浅谈Targan算法

Targan算法是用来处理强连通问题(a->b且b->a)

Targan算法里面需要定义两个数组dfn与low并通过栈来实现.

1，dfn[x]: x是第几个入栈的。
2，low[x]: 节点x能够回溯到的最早位于栈中的节点。
判断结束的条件就是当满足low[x]==dfn[x]；可以理解为low[x]经过一系列的转换还是回到自身说明这个环（通过栈来实现）里面的元素可以构成强连通

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int v,next;
 8 } edge[1001];
 9 int DFN[1001],LOW[1001];
10 int stack[1001],heads[1001],visit[1001],cnt,tot,index;
11 void add(int x,int y)//链式前向心
12 {
13     edge[++cnt].next=heads[x];
14     edge[cnt].v = y;
15     heads[x]=cnt;
16     return ;
17 }
18 void tarjan(int x)//代表第几个点在处理。递归的是点。
19 {
20     DFN[x]=LOW[x]=++tot;
21     stack[++index]=x;
22     visit[x]=1;//表示在栈里
23     for(int i=heads[x]; ~i ;i=edge[i].next)
24     {
25         if(!DFN[edge[i].v])  //如果没访问过
26         {
27             tarjan(edge[i].v);//往下进行延伸，开始递归
28             LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。
29         }
30         else if(visit[edge[i].v ])   //如果访问过，并且还在栈里。
31         {
32             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系
33         }
34     }
35     if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。
36     {
37         do
38         {
39             printf("%d ",stack[index]);
40             visit[stack[index]]=0;
41             index--;
42         }
43         while(x!=stack[index+1]); //出栈，直到找到最小根。
44         printf("
");
45     }
46     return ;
47 }
48 int main()
49 {
50     memset(heads,-1,sizeof(heads));
51     int n,m;
52     scanf("%d%d",&n,&m);
53     int x,y;
54     for(int i=1; i<=m; i++)
55     {
56         scanf("%d%d",&x,&y);
57         add(x,y);
58     }
59     for(int i=1; i<=n; i++)
60         if(!DFN[i])tarjan(i);//当这个点没有访问过，就从此点开始。防止图没走完
61     return 0;
62 }

代码运行过程如下所示：

可以观察到，targan算法主要就是通过low[]来进行转移，dfn[x]可以看成第几个入栈，判断当low[x]==dfn[x]的时候就出栈。