强连通分量 ZQUOJ 21467&&POJ 2553 The Bottom of a Graph

Description

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V x V, its elements being called edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e₁, ... , e_n) be a sequence of length n of edges e_i E such that e_i= (v_i,v_i+1) for a sequence of vertices ( v₁,... , v_n+1). Then p is called a path from vertex v₁ to vertex v_n+1 in G and we say that v_n+1 is reachable from v₁, writing ( v₁ v_n+1).
Here are some new definitions. A node v in a graph G=( V, E ) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G) = { vV | w∈V: (vw) (wv) }. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=( V, E ), where the vertices will be identified by the integer numbers in the set V={ 1 , ... , v }. You may assume that 1 <= v <= 5000. That is followed by a non-negative integer e and, thereafter,e pairs of vertex identifiers v₁, w₁, ... , v_e, w_e with the meaning that (v_i, w_i) E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output

1 3
2

题目大意，给定一个有向图，按顺序输出“自己可达的顶点都可到达自己”的顶点。

解题思路：先求出图的强连通分量，缩点，求出度为0的强连通分量中的顶点，并按按顺序输出。

有关强强连通分量的算法请参考：http://www.byvoid.com/blog/scc-tarjan/（Tarjan算法）

http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591370.html（Tarjan，Kosaraju，Garbow）

http://blog.csdn.net/liguanxing/article/details/5665520（Kosaraju算法）

http://hi.baidu.com/yy17yy/item/8f4142dee291e6ee3cc2cb2f（Garbow算法）

AC代码（Tarjan）：

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 typedef struct
 4 {
 5     int v,next;
 6 }Node;
 7 Node e[50000];
 8 int n,m,index,top,count;
 9 int first[5001],DFN[5001],Low[5001],ver[5001];
10 int belong[5001],stack[5001],instack[5001],val[5001],degree[5001];
11 void Tarjan(int i)
12 {
13     int k,j,v;
14     DFN[i]=Low[i]=index++;
15     instack[i]=true;
16     stack[top++]=i;
17     for(j=first[i];j!=-1;j=e[j].next)
18     {
19         k=e[j].v;
20         if(!DFN[k])
21         {
22             Tarjan(k);
23             if(Low[k]<Low[i])
24                 Low[i]=Low[k];
25         }
26         else if(instack[k]&&DFN[k]<Low[i])
27             Low[i]=DFN[k];
28     }
29     if(Low[i]==DFN[i])
30     {
31         count++;
32         do{
33             v=stack[--top];
34             instack[v]=false;
35             belong[v]=count;
36             val[count]++;
37         }while(i!=v);
38     }
39 }
40 int main()
41 {
42     int g,i,j,u,v;
43     while(scanf("%d",&n)&&n)
44     {
45         scanf("%d",&m);
46         g=0; index=0; top=0; count=0;
47         memset(first,-1,sizeof(first));
48         memset(DFN,0,sizeof(DFN));
49         memset(Low,0,sizeof(Low));
50         memset(degree,0,sizeof(degree));
51         for(i=0;i<m;i++)
52         {
53             scanf("%d%d",&u,&v);
54             e[g].v=v;
55             e[g].next=first[u];
56             first[u]=g++;
57         }
58         for(i=1;i<=n;i++)
59             if(!DFN[i])
60                 Tarjan(i);
61         for(i=1;i<=n;i++)
62             for(j=first[i];j!=-1;j=e[j].next)
63             {
64                 v=e[j].v;
65                 if(belong[i]!=belong[v])
66                     degree[belong[i]]++;
67             }
68         for(i=1;i<=n;i++)
69         {
70             if(!degree[belong[i]])
71                 printf("%d ",i);
72         }
73         printf("\n");
74     }
75     return 0;
76 }

AC代码（Kosaraju）：

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 typedef struct
 4 {
 5     int u,v,next1,next2;
 6 }Node;
 7 Node e[50000];
 8 int n,m,index;
 9 int first1[5001],first2[5001],vis[5001],belong[5001],num[5001],degree[5001];
10 void dfs1(int i)
11 {
12     int j,k;
13     vis[i]=1;
14     for(j=first1[i];j!=-1;j=e[j].next1)
15     {
16         k=e[j].v;
17         if(!vis[k])
18             dfs1(k);
19     }
20     num[index++]=i;
21 }
22 void dfs2(int i)
23 {
24     int j,k;
25     vis[i]=1;
26     belong[i]=index;
27     for(j=first2[i];j!=-1;j=e[j].next2)
28     {
29         k=e[j].u;
30         if(!vis[k])
31             dfs2(k);
32     }
33 }
34 void kosaraju()
35 {
36     int i;
37     index=1;
38     memset(vis,0,sizeof(vis));
39     for(i=1;i<=n;i++)
40         if(!vis[i])
41             dfs1(i);
42     index=1;
43     memset(vis,0,sizeof(vis));
44     for(i=n;i>=1;i--)
45         if(!vis[num[i]])
46         {
47             dfs2(num[i]);
48             index++;
49         }
50 }
51 int main()
52 {
53     int g,i,j,u,v;
54     while(scanf("%d",&n)&&n)
55     {
56         g=0;
57         memset(first1,-1,sizeof(first1));
58         memset(first2,-1,sizeof(first2));
59         memset(degree,0,sizeof(degree));
60         scanf("%d",&m);
61         for(i=1;i<=m;i++)
62         {
63             scanf("%d%d",&u,&v);
64             e[g].v=v;
65             e[g].next1=first1[u];
66             first1[u]=g;
67             e[g].u=u;
68             e[g].next2=first2[v];
69             first2[v]=g++;
70         }
71         kosaraju();
72         for(i=1;i<=n;i++)
73             for(j=first1[i];j!=-1;j=e[j].next1)
74             {
75                 v=e[j].v;
76                 if(belong[i]!=belong[v])
77                     degree[belong[i]]++;
78             }
79         for(i=1;i<=n;i++)
80             if(!degree[belong[i]])
81                 printf("%d ",i);
82         printf("\n");
83     }
84     return 0;
85 }

AC代码（Garbow)：

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 typedef struct
 4 {
 5     int v,next;
 6 }Node;
 7 Node e[50000];
 8 int n,m,index,top1,top2,count;
 9 int first[5001],low[5001],stack1[5001],stack2[5001];
10 int belong[5001],degree[5001];
11 void Garbow(int i)
12 {
13     int j,k;
14     stack1[++top1]=stack2[++top2]=i;
15     low[i]=index++;
16     for(j=first[i];j!=-1;j=e[j].next)
17     {
18         k=e[j].v;
19         if(!low[k])
20             Garbow(k);
21         else if(!belong[k])
22         {
23             while(low[stack2[top2]]>low[k])
24                 top2--;
25         }
26     }
27     if(stack2[top2]==i)
28     {
29         top2--;
30         count++;
31         do{
32             k=stack1[top1--];
33             belong[k]=count;
34         }while(k!=i);
35     }
36 }
37 int main()
38 {
39     int g,i,j,u,v;
40     while(scanf("%d",&n)&&n)
41     {
42         scanf("%d",&m);
43         g=0; top1=top2=-1; index=1; count=0;
44         memset(first,-1,sizeof(first));
45         memset(low,0,sizeof(low));
46         memset(belong,0,sizeof(belong));
47         memset(degree,0,sizeof(degree));
48         for(i=1;i<=m;i++)
49         {
50             scanf("%d%d",&u,&v);
51             e[g].v=v;
52             e[g].next=first[u];
53             first[u]=g++;
54         }
55         for(i=1;i<=n;i++)
56             if(!low[i])
57                 Garbow(i);
58         for(i=1;i<=n;i++)
59             for(j=first[i];j!=-1;j=e[j].next)
60             {
61                 v=e[j].v;
62                 if(belong[i]!=belong[v])
63                     degree[belong[i]]++;
64             }
65         for(i=1;i<=n;i++)
66             if(!degree[belong[i]])
67                 printf("%d ",i);
68         printf("\n");
69     }
70     return 0;
71 }