题目大意，给定一个有向图，按顺序输出“自己可达的顶点都可到达自己”的顶点。
由于没有按顺序输出，WA了一次。
View Code
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <memory.h>
4 #define CLR(a) (memset(a,0,sizeof(a)))
5 #define N 5001
6 struct node
7 {
8 int v;
9 struct node *next;
10 };
11 struct node *in[N],*out[N];
12 char vis[N];
13 int ord[N],id[N],d[N],n,m,cnt;
14 void addEdge(int u,int v)
15 {
16 struct node *p,*q;
17 p=(struct node*)malloc(sizeof(struct node));
18 q=(struct node*)malloc(sizeof(struct node));
19 p->v=v;
20 p->next=out[u],out[u]=p;
21 q->v=u;
22 q->next=in[v],in[v]=q;
23 }
24 void dfs(int u)
25 {
26 int v;
27 struct node *p=out[u];
28 vis[u]=1;
29 while(p)
30 {
31 v=p->v;
32 if(!vis[v]) dfs(v);
33 p=p->next;
34 }
35 ord[++cnt]=u;
36 }
37 void rdfs(int u)
38 {
39 int v;
40 struct node *p=in[u];
41 vis[u]=1,id[u]=cnt;
42 while(p)
43 {
44 v=p->v;
45 if(!vis[v]) rdfs(v);
46 p=p->next;
47 }
48 }
49 void kosaraju()
50 {
51 int i,j,t;
52 struct node *p;
53 CLR(vis);
54 for(i=1,cnt=0; i<=n; i++)
55 {
56 if(!vis[i]) dfs(i);
57 }
58 CLR(vis);
59 for(t=n,cnt=0; t>0; t--)
60 {
61 i=ord[t];
62 if(!vis[i])
63 {
64 cnt++;
65 rdfs(i);
66 }
67 }
68 CLR(d);
69 for(i=1; i<=n; i++)
70 {
71 p=out[i];
72 while(p)
73 {
74 j=p->v;
75 if(id[i]!=id[j]) d[id[i]]++;
76 p=p->next;
77 }
78 }
79 t=0;
80 for(j=1; j<=n; j++)
81 {
82 if(d[id[j]]==0)
83 {
84 if(t) printf(" %d",j);
85 else t=1,printf("%d",j);
86 }
87 }
88 printf("\n");
89 for(i=1; i<=n; i++)
90 {
91 p=out[i];
92 while(p)
93 {
94 out[i]=p->next,free(p),p=out[i];
95 }
96 p=in[i];
97 while(p)
98 {
99 in[i]=p->next,free(p),p=in[i];
100 }
101 }
102 }
103 int main()
104 {
105 int i,a,b;
106 while(scanf("%d%d",&n,&m)!=EOF)
107 {
108 for(i=0; i<m; i++)
109 {
110 scanf("%d%d",&a,&b);
111 addEdge(a,b);
112 }
113 kosaraju();
114 }
115 return 0;
116 }