【题意】：给出一个有向图，定义：若节点u所有能到达的点v，都能反过来到达u，那么称节点u是sink，求所有的sink点。
【题解】：先求出强连通分支图Gscc，然后在Gscc图中找到所有的出度为0的强连通分支。这分支里面的所有点都是sink点。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 using namespace std;
6 #define maxn 5005
7 #define maxm 100005
8
9 int tot, dfn[maxn], low[maxn], Dindex, instack[maxn], belong[maxn], cnt;
10 int s[2*maxn], top;
11 int eh[maxn], n, m, out[maxn], ans[maxn];
12
13 struct Edge {
14 int v, next;
15 }et[maxm];
16
17 void addedge(int u, int v) {
18 Edge E = {v, eh[u]};
19 et[tot] = E;
20 eh[u] = tot++;
21 }
22
23 void init() {
24 tot = 0;
25 memset(eh, -1, sizeof(eh));
26 }
27
28 void tarjan(int u) {
29 int v;
30 dfn[u] = low[u] = ++Dindex;
31 instack[u] = true;
32 s[++top] = u;
33 for(int i = eh[u]; i != -1; i = et[i].next) {
34 v = et[i].v;
35 if(!dfn[v]) {
36 tarjan(v);
37 if(low[v] < low[u]) low[u] = low[v];
38 } else if(instack[v] && dfn[v] < low[u]) low[u] = dfn[v];
39 }
40 if(dfn[u] == low[u]) {
41 cnt++;
42 do {
43 v = s[top--];
44 instack[v] = false;
45 belong[v] = cnt;
46 }while(v != u);
47 }
48 }
49
50 void solve() {
51 tot = cnt = Dindex = 0;
52 memset(dfn, 0, sizeof(dfn));
53 memset(instack, 0, sizeof(instack));
54 for(int i = 1; i <= n; i++)
55 if(!dfn[i]) tarjan(i);
56 }
57
58 int main() {
59 while(cin >> n) {
60 if(!n) break;
61 init();
62 cin >> m;
63 for(int i = 0; i < m; i++) {
64 int u, v;
65 cin >> u >> v;
66 addedge(u, v);
67 }
68 solve();
69 memset(out, 0, sizeof(out));
70 for(int i = 1; i <= n; i++) {
71 for(int j = eh[i]; j != -1; j = et[j].next) {
72 int v = et[j].v;
73 if(belong[i] != belong[v]) out[belong[i]]++;
74 }
75 }
76 int index = 0;
77 for(int i = 1; i <= n; i++) {
78 if(out[belong[i]] == 0)
79 ans[index++] = i;
80 }
81 sort(ans, ans + index);
82 for(int i = 0; i < index; i++)
83 printf("%d ", ans[i]);
84 printf("\n");
85 }
86 return 0;
87 }