http://poj.org/problem?id=2553
强连通简单题，难点在于对题意的理解上，尤其是这句话 if for every node w in G that is reachable from v, v is also reachable from w. 是说在v可以到达的所有点也都可以到达v,由此就可以知道求解缩点以后出度为0的点中的节点数字即可，并且本题不存在出题者说的bottom为空的情况，DAG肯定有出度为0的节点。
tarjan代码
View Code
1 #include <iostream>
2 #include <memory.h>
3 #include <algorithm>
4 using namespace std;
5 #define MIN(a,b) ((a)<(b)?(a):(b))
6 const int SIZE=5001;
7 struct node
8 {
9 int end;
10 node*next;
11 }edge[SIZE*SIZE],*head[SIZE],*p;
12 int sum,numedge,cnt,father;
13 int dfn[SIZE],low[SIZE],stack[SIZE],belong[SIZE];
14 bool is_stack[SIZE];
15 int out[SIZE];
16 void add(int a,int b)
17 {
18 p->end=b;
19 p->next=head[a];
20 head[a]=p++;
21 }
22 void tarjan(int key)
23 {
24 dfn[key]=low[key]=++cnt;
25 stack[++stack[0]]=key;
26 is_stack[key]=true;
27 for(node*tmp=head[key];tmp;tmp=tmp->next)
28 {
29 if(!low[tmp->end])
30 {
31 tarjan(tmp->end);
32 low[key]=MIN(low[key],low[tmp->end]);
33 }
34 else if(is_stack[tmp->end])
35 low[key]=MIN(low[key],low[tmp->end]);
36 }
37 if(dfn[key]==low[key])
38 {
39 ++father;
40 do
41 {
42 belong[stack[stack[0]]]=father;
43 is_stack[stack[stack[0]]]=false;
44 }
45 while(stack[stack[0]--]!=key);
46 }
47 }
48 void ini()
49 {
50 memset(head,NULL,sizeof(head));
51 memset(stack,0,sizeof(stack));
52 memset(belong,0,sizeof(belong));
53 memset(dfn,0,sizeof(dfn));
54 memset(low,0,sizeof(low));
55 memset(is_stack,false,sizeof(is_stack));
56 memset(out,0,sizeof(out));
57 }
58 int main()
59 {
60 while(scanf("%d",&sum)==1&&sum)
61 {
62 scanf("%d",&numedge);
63 p=edge;
64 for(int i=0,a,b;i<numedge;++i)
65 {
66 scanf("%d %d",&a,&b);
67 add(a,b);
68 }
69
70 father=cnt=0;
71 for(int i=1;i<=sum;++i)
72 if(!low[i])
73 tarjan(i);
74 for(int i=1;i<=sum;++i)
75 for(node*tmp=head[i];tmp;tmp=tmp->next)
76 if(belong[i]!=belong[tmp->end])
77 ++out[belong[i]];
78 int tmp[SIZE],k=0;
79 for(int i=1;i<=father;++i)
80 if(!out[i])
81 tmp[k++]=i;
82 if(k)
83 {
84 int array[SIZE];
85 cnt=0;
86 for(int i=1;i<=sum;++i)
87 for(int j=0;j<k;++j)
88 if(belong[i]==tmp[j])
89 array[cnt++]=i;
90 sort(array,array+cnt);
91 printf("%d",array[0]);
92 for(int i=1;i<cnt;++i)
93 printf(" %d",array[i]);
94 }
95 printf("\n");
96 ini();
97 }
98 return 0;
99 }
Gabow代码
View Code
1 #include <iostream>
2 #include <memory.h>
3 #include <algorithm>
4 using namespace std;
5 #define MIN(a,b) ((a)<(b)?(a):(b))
6 const int SIZE=5001;
7 struct node
8 {
9 int num;
10 node*next;
11 }edge[SIZE*SIZE],*head[SIZE],*p;
12 int sum,numedge,cnt,father;
13 int init[SIZE],root_stack[SIZE],stack[SIZE],belong[SIZE];
14 int out[SIZE];
15 void add(int a,int b)
16 {
17 p->num=b;
18 p->next=head[a];
19 head[a]=p++;
20 }
21 void Gabow(int key)
22 {
23 root_stack[++root_stack[0]]=stack[++stack[0]]=key;
24 init[key]=++cnt;
25 for(node*tmp=head[key];tmp;tmp=tmp->next)
26 {
27 if(!init[tmp->num])
28 Gabow(tmp->num);
29 else if(!belong[tmp->num])
30 while(init[root_stack[root_stack[0]]]>init[tmp->num])
31 root_stack[0]--;
32 }
33 if(key==root_stack[root_stack[0]])
34 {
35 ++father,--root_stack[0];
36 do
37 belong[stack[stack[0]]]=father;
38 while(stack[stack[0]--]!=key);
39 }
40 }
41 void ini()
42 {
43 memset(belong,0,sizeof(belong));
44 memset(stack,0,sizeof(stack));
45 memset(root_stack,0,sizeof(root_stack));
46 memset(head,NULL,sizeof(head));
47 memset(init,0,sizeof(init));
48 memset(out,0,sizeof(out));
49 }
50 int main()
51 {
52 while(scanf("%d",&sum)==1&&sum)
53 {
54 scanf("%d",&numedge);
55 p=edge;
56 for(int i=0,a,b;i<numedge;++i)
57 {
58 scanf("%d %d",&a,&b);
59 add(a,b);
60 }
61 father=cnt=0;
62 for(int i=1;i<=sum;++i)
63 if(!init[i])
64 Gabow(i);
65 for(int i=1;i<=sum;++i)
66 for(node*tmp=head[i];tmp;tmp=tmp->next)
67 if(belong[i]!=belong[tmp->num])
68 ++out[belong[i]];
69 int tmp[SIZE],k=0;
70 for(int i=1;i<=father;++i)
71 if(!out[i])
72 tmp[k++]=i;
73 if(k)
74 {
75 int array[SIZE];
76 cnt=0;
77 for(int i=1;i<=sum;++i)
78 for(int j=0;j<k;++j)
79 if(belong[i]==tmp[j])
80 array[cnt++]=i;
81 sort(array,array+cnt);
82 printf("%d",array[0]);
83 for(int i=1;i<cnt;++i)
84 printf(" %d",array[i]);
85 }
86 printf("\n");
87 ini();
88 }
89 return 0;
90 }