HDU 3639 Hawk-and-Chicken

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 5100;
 4 struct arc {
 5     int to,next;
 6     arc(int x = 0,int y = -1) {
 7         to = x;
 8         next = y;
 9     }
10 } e[100010];
11 int head[maxn],dfn[maxn],low[maxn],cnt[maxn],clk,scc,tot;
12 int belong[maxn],du[maxn],fan[maxn],n,m;
13 bool instack[maxn];
14 stack<int>stk;
15 vector<int>g[maxn];
16 void add(int u,int v) {
17     e[tot] = arc(v,head[u]);
18     head[u] = tot++;
19 }
20 void tarjan(int u) {
21     dfn[u] = low[u] = ++clk;
22     instack[u] = true;
23     stk.push(u);
24     for(int i = head[u]; ~i; i = e[i].next) {
25         if(!dfn[e[i].to]) {
26             tarjan(e[i].to);
27             low[u] = min(low[u],low[e[i].to]);
28         } else if(instack[e[i].to]) low[u] = min(low[u],dfn[e[i].to]);
29     }
30     if(low[u] == dfn[u]) {
31         int v;
32         cnt[++scc] = 0;
33         do {
34             instack[v = stk.top()] = false;
35             stk.pop();
36             belong[v] = scc;
37             cnt[scc]++;
38         } while(v != u);
39     }
40 }
41 bool vis[maxn];
42 void init() {
43     for(int i = tot = clk = scc = 0; i < maxn; ++i) {
44         head[i] = -1;
45         dfn[i] = low[i] = belong[i] = 0;
46         instack[i] = false;
47         g[i].clear();
48         fan[i] = du[i] = 0;
49     }
50 }
51 int dfs(int u) {
52     vis[u] = true;
53     int ret = cnt[u];
54     for(int i = g[u].size()-1; i >= 0; --i) {
55         if(vis[g[u][i]]) continue;
56         ret += dfs(g[u][i]);
57     }
58     return ret;
59 }
60 int main() {
61     int kase,u,v,cs = 1;
62     scanf("%d",&kase);
63     while(kase--) {
64         scanf("%d%d",&n,&m);
65         init();
66         for(int i = 0; i < m; ++i) {
67             scanf("%d%d",&u,&v);
68             add(u,v);
69         }
70         for(int i = 0; i < n; ++i)
71             if(!dfn[i]) tarjan(i);
72         for(int i = 0; i < n; ++i) {
73             for(int j = head[i]; ~j; j = e[j].next) {
74                 if(belong[i] == belong[e[j].to]) continue;
75                 g[belong[e[j].to]].push_back(belong[i]);
76                 du[belong[i]]++;
77             }
78         }
79         int mx = -1;
80         for(int i = 1; i <= scc; ++i)
81             if(!du[i]) {
82                 memset(vis,false,sizeof vis);
83                 fan[i] = dfs(i) - 1;
84                 mx = max(mx,fan[i]);
85             }
86         bool flag = true;
87         printf("Case %d: %d\n",cs++,mx);
88         for(int i = 0; i < n; ++i)
89             if(fan[belong[i]] == mx) {
90                 if(flag) {
91                     printf("%d",i);
92                     flag = false;
93                 } else printf(" %d",i);
94             }
95         puts("");
96     }
97     return 0;
98 }