這類題目遇到好幾條了，不想解釋了，藍(lán)皮書上有個(gè)學(xué)校軟件援助計(jì)劃，poj上也有原題，這題太裸了，不解釋。。
1 # include <stdio.h>
2 # include <string.h>
3 # include <stdbool.h>
4 # include <stdlib.h>
5 # define min(a,b) ((a)<(b)?(a):(b))
6 bool map[5005][5005];
7 int n,m;
8 int dfn,id[5005],low[5005],con[5005],cn,stack[5005],top,res[5005],rc;
9 bool count[5005];
10 int cmp(const void *a,const void *b)
11 {
12 return *(int *)a-*(int *)b;
13 }
14 void dfs(int pos)
15 {
16 int i;
17 id[pos]=low[pos]=dfn++;
18 stack[top++]=pos;
19 for(i=1;i<=n;i++)
20 if(map[pos][i])
21 {
22 if(id[i]==-1)
23 dfs(i);
24 low[pos]=min(low[pos],low[i]);
25 }
26 if(low[pos]>=id[pos])
27 {
28 do
29 {
30 con[stack[--top]]=cn;
31 low[stack[top]]=n;
32 }while(stack[top]!=pos);
33 cn++;
34 }
35 }
36 int main()
37 {
38 // freopen("bottom.in","r",stdin);
39 // freopen("ans.txt","w",stdout);
40 while(1)
41 {
42 int i,j;
43 scanf("%d",&n);
44 if(!n) break;
45 scanf("%d",&m);
46 memset(map,0,sizeof(map));
47 while(m--)
48 {
49 int t1,t2;
50 scanf("%d%d",&t1,&t2);
51 map[t1][t2]=1;
52 }
53 dfn=cn=top=rc=0;
54 memset(id,-1,sizeof(id));
55 for(i=1;i<=n;i++)
56 if(id[i]==-1)
57 dfs(i);
58 memset(count,1,sizeof(count));
59 for(i=1;i<=n;i++)
60 if(count[con[i]])
61 for(j=1;j<=n;j++)
62 if(map[i][j]&&con[i]!=con[j])
63 {
64 count[con[i]]=0;
65 }
66 for(i=0;i<cn;i++)
67 if(count[i])
68 {
69 for(j=1;j<=n;j++)
70 if(con[j]==i)
71 res[rc++]=j;
72 }
73 qsort(res,rc,sizeof(int),cmp);
74 if(rc==0)
75 printf("\n");
76 else
77 {
78 printf("%d",res[0]);
79 for(i=1;i<rc;i++)
80 printf(" %d",res[i]);
81 printf("\n");
82 }
83
84 }
85 return 0;
86 }
87