NOIp 2015信息传递【tarjan/拓扑/并查集】

一道好的NOIp题目，在赛场上总能用许多算法A掉。比如这道和关押罪犯。

法一：tarjan在有向图中跑最小环

有人从别人口中得知自己信息，等效于出现了一个环。于是这就变成了一个有向图tarjan强连通分量的板子题。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<stack>
 4 #define maxn 200090
 5 
 6 using namespace std;
 7 
 8 int n,y,tot,ans=999999,dfs_clock,scc_cnt,tong[maxn],dfn[maxn],low[maxn],head[maxn],scc[maxn]; 
 9 stack<int>s;
10 struct node{
11     int to,next;
12 }edge[maxn];
13 
14 void add(int x,int y)
15 {
16     edge[++tot].to=y;
17     edge[tot].next=head[x];
18     head[x]=tot;
19 }
20 
21 void dfs(int p)
22 {
23     dfn[p]=low[p]=++dfs_clock;
24     s.push(p);
25     for(int i=head[p];i;i=edge[i].next)
26     {
27         int y=edge[i].to;
28         if(!dfn[y])
29         {
30             dfs(y);
31             low[p]=min(low[p],low[y]);
32         }
33         else if(!scc[y]) low[p]=min(low[p],dfn[y]);
34     }
35     if(dfn[p]==low[p])
36     {
37         scc_cnt++;
38         while(1)
39         {
40             int x=s.top();
41             s.pop();
42             scc[x]=scc_cnt;
43             if(x==p) break;
44         }
45     }
46 }
47 
48 int main()
49 {
50     scanf("%d",&n);
51     for(int i=1;i<=n;i++)
52      scanf("%d",&y),add(i,y);
53     for(int i=1;i<=n;i++)
54     {
55         if(!dfn[i]) dfs(i);
56         tong[scc[i]]++;
57     }
58     for(int i=1;i<=scc_cnt;i++) if(tong[i]>1&&tong[i]<ans) ans=tong[i];
59     printf("%d
",ans);
60     return 0;
61 }

View Code

法二：拓扑排序

图中可能会出现很多环，求最小的一个。我们跑一遍拓扑排序后，那些不曾入到队列中的点就是成环的点。于是我们可以边拓扑排序边标记最后找到那些在环上的点，从他们出发分别求出环的大小进行比较。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 
 5 using namespace std;
 6 
 7 int n,x,ans=999999,cnt,tot;
 8 int du[200090],head[200090],vis[200090],flag[200090];
 9 struct node{
10     int to,next;
11 }edge[200090];
12 queue<int>q;
13 
14 void add(int x,int y)
15 {
16     edge[++tot].next=head[x];
17     edge[tot].to=y;
18     head[x]=tot;
19 }
20 
21 void topo()
22 {
23     for(int i=1;i<=n;i++)
24         if(!du[i]) q.push(i),flag[i]=1;
25     while(!q.empty())
26     {
27         int u=q.front();q.pop();
28         for(int i=head[u];i;i=edge[i].next)
29         {
30             int v=edge[i].to;
31             if(--du[v]==0) q.push(v),flag[v]=1;
32         }
33     }
34 }
35 
36 void dfs(int x)
37 {
38     vis[x]=1,cnt++;
39     for(int i=head[x];i;i=edge[i].next)
40     {
41         int y=edge[i].to;
42         if(vis[y]) return ;
43         dfs(y);
44     }
45 }
46 
47 int main()
48 {
49     scanf("%d",&n);
50     for(int i=1;i<=n;i++)
51         scanf("%d",&x),add(i,x),du[x]++;
52     topo();
53     for(int i=1;i<=n;i++)
54         if((!flag[i])&&(!vis[i]))
55         {
56             cnt=0;
57             dfs(i);
58             ans=min(ans,cnt);
59         }
60     printf("%d",ans);
61     return 0;
62 }

View Code

法三：并查集

https://anyway.blog.luogu.org/solution-p2661