信息传递

noip2015d1t2。

原题链接:https://www.luogu.org/problem/show?pid=2661

这道题其实是让你求一个图中最小环的长度。正常向方法是搜索+剪枝,不过也有一个叫tarjan的算法,可以用来求强联通分量。

两个方法我都说一下吧。

正常向方法:

1.建图,这里一般用邻接表,当然不用也行,因为就这个题来说没必要记录这么多信息,只记录某个点的连接的下一个点的编号就行了,我这里就没写正常邻接表。

2.以每个点为起点进行一次DFS。这里有一步判环操作:打标记,也就是所谓的时间戳,判环用的。每次扩展节点的时候查看一下这个点是不是有时间戳,如果有那就说明这个点曾经扩展过,那就是成环了。把以所有点出发的环的长度求出来,取一个最小值就是答案。应该需要队列。

(我要是没记错的话STL队列会T,所以建议手写队列)

我使用了拓扑排序,显然题中的这个图一定是个DAG,所以在拓扑排序的时候,我们要不断地找入边,这样可以删除不成环的边,删完后就剩下一个个的环。

再在这些环上用DFS求最小环长度就好了。

第二种方法是用tarjan算法求强联通分量。这个算法是由一个名叫tarjan的人提出来的,由他的名字命名 (但这个词到底怎么读,我遇到过好多版本的)。。

先说一下什么叫强联通分量。如果两个顶点可以相互通达,则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。

tarjan算法可以在线性时间复杂度内求出一个有向图的强联通分量。

Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。

搜索时,把当前搜索树中未处理的节点放到一个栈里面,在回溯的时候就可以判断栈顶到栈中的节点是否为一个强连通分量。

为了方便,我们定义(好多文章中都是以这个名字定义的,我也就沿用了):

dfn[ i ] 为在DFS中该节点被搜索的次序,也就是时间戳。

low[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号。

可以证明,当dfn[ i ]=low[ i ]时,i或i的子树可以构成一个强连通分量。

  具体演示过程,可以参考这位BYVoid博主写的博文:https://www.byvoid.com/zhs/blog/scc-tarjan

  这里给出分别使用两种方法的AC代码:

  1.正常向:

  

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #define maxn 200005
 6 #define INF 1e9+7;
 7 using namespace std;
 8 int n;
 9 int d[maxn],vis[maxn],to[maxn],q[maxn];
10 /*
11 d数组记录某个点的入度
12 vis数组便是标记数组
13 to数组记录从某个点出发指向哪里,因为按照题意每个点的目标只有一个
14 q为一般队列
15  */
16 int ans=INF;
17 inline int read(){
18     int num = 0;
19     char c;
20     bool flag = false;
21     while ((c = getchar()) == ' ' || c == '
' || c == '
');
22         if (c == '-') flag = true;
23     else
24         num = c - '0';
25     while (isdigit(c = getchar()))
26     num = num * 10 + c - '0';
27     return (flag ? -1 : 1) * num;
28 }
29 void tppx(void){
30     int head=0;
31     int tail=0;
32     for (int i=1;i<=n;i++)//拓扑排序先标记一下入度为0的点
33         if (d[i] == 0){
34             vis[i] = 1;
35             q[++tail] = i;
36         }
37     while (head<tail){//从入度为0的点开始BFS
38         int now=q[++head];//取队首并弹出队首,简化写法,以下同
39         d[to[now]]--;//每次取了一条边也可看作删掉了这条边,入度-1
40         if(d[to[now]]==0){//如果下一个连接的点也入度为0了,那么再以这个点进行BFS(想一下拓扑排序的主过程)
41             vis[to[now]] = 1;
42             q[++tail] = to[now];
43         }
44     }
45 }
46 void dfs(int now,int k){//以每个点为起点遍历整个图,k用来记录当前的长度,求一个最小的ans就是答案
47     vis[now] = 1;
48     if (vis[to[now]]==0)
49         dfs(to[now],k+1);
50     else
51         ans = min(ans,k);
52 
53 }
54 int main(){//主过程就很明显了吧
55     n = read();
56     for (int i=1;i<=n;i++){
57         to[i] = read();
58         d[to[i]]++;
59     }
60     tppx();
61     for (int i=1;i<=n;i++){
62         if (!vis[i])
63             dfs(i,1);
64     }
65     cout << ans << endl;
66     return 0;    
67 }

  

  2.使用tarjan算法:

  

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 200005
 6 #define INF 1e9+7;
 7 using namespace std;
 8 int n;
 9 int ans=INF;
10 int s[maxn],top=0;
11 int dfn[maxn],low[maxn],tot=0;
12 int head[maxn],cnt=0;
13 int vis[maxn];
14 struct Edge{//这里我用了正常邻接表
15     int from;
16     int to;
17 };
18 Edge edge[maxn];
19 inline int read(){//到哪都少不了的快读
20     int num = 0;
21     char c;
22     bool flag = false;
23     while ((c = getchar()) == ' ' || c == '
' || c == '
');
24         if (c == '-') flag = true;
25     else
26         num = c - '0';
27     while (isdigit(c = getchar()))
28     num = num * 10 + c - '0';
29     return (flag ? -1 : 1) * num;
30 }
31 void add_edge(int from,int to){
32     edge[++cnt].from=head[from];
33     edge[cnt].to = to;
34     head[from]=cnt;
35 }
36 void tarjan(int u){
37     vis[u]=1;
38     dfn[u]=low[u]=++tot;
39     s[++top]=u;
40     for(int i=head[u];i!=0;i=edge[i].from){
41         int v = edge[i].to;
42         if(!dfn[v]){
43             tarjan(v);
44             low[u]=min(low[u],low[v]);
45         }
46         else if(vis[v]) 
47             low[u]=min(low[u],dfn[v]);
48     }
49     if(low[u]==dfn[u]){
50         int temp=0;
51         do{
52             vis[s[top]]=0;
53             temp++;
54         }while(s[top--] != u);
55         if(temp!=1) 
56             ans=min(ans,temp);
57     }
58 }
59 int main(){
60     n = read();
61     for(int u=1;u<=n;u++){
62         int v;
63         v = read();
64         add_edge(u,v);
65     }
66     for(int i=1;i<=n;i++)//依然是每个点都要考虑,从每个点出发求一遍连通分量取最小值
67         if(!dfn[i]) 
68             tarjan(i);
69     cout << ans << endl;
70     return 0;
71 }
原文地址:https://www.cnblogs.com/OIerShawnZhou/p/7451095.html