大學班級選班長，N 個同學均可以發表意見 若意見為 A B 則表示 A 認為 B 合适，意見具有傳遞性，即 A 認為 B 合适，B 認為 C 合适，則 A 也認為 C 合适 勤勞的 TT 收集了M條意見，想要知道最高票數，并給出一份候選人名單，即所有得票最多的同學，你能幫幫他嗎？
Input
本題有多組資料。第一行 T 表示資料組數。每組資料開始有兩個整數 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下來有 M 行包含兩個整數 A 和 B(A != B) 表示 A 認為 B 合适。
Output
對于每組資料，第一行輸出 “Case x: ”，x 表示資料的編号，從1開始，緊跟着是最高的票數。 接下來一行輸出得票最多的同學的編号，用空格隔開，不忽略行末空格！
Sample Input
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2
Sample Output
Case 1: 2
0 1
Case 2: 2
0 1 2
解題思路：
targin縮點後 得到一個DAG(有向無環圖，順便記錄下每個強連通圖包含的節點數)，每個強連通圖可以用一個唯一編号去代替，這樣可以知道有多少個強連通圖是沒有出度的，我們的答案就在這些 沒有出度的強連通圖中。因為如果一個強連通圖有出度，那麼它一定不是得票最多的。
縮點後，不難發現對于屬于第 i 個 SCC 的點來說，答案分為 兩部分，令 SCC[i] 表示第 i 個 SCC 中點的個數
• 目前 SCC 中的點，ans += SCC[i] – 1（去除自己）
• 其它 SCC 中的點 • SUM ( SCC[j] )，其中 j 可到達 I
• 稍加思考，可以發現最後答案一定出現在出度為 0 的 SCC 中
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const int INF = 1e8;
const int maxn = 5010;
vector<int> G1[maxn],G2[maxn];
int low[maxn],dfn[maxn],in[maxn];
int vis[maxn],instack[maxn],scc[maxn],ans[maxn],sccsum[maxn];
int n,tot,num,sum;
stack<int> S;
void init(){
tot = num = 0;
for(int i=0 ;i<=n ;i++){
G1[i].clear(),G2[i].clear();
}
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(in,0,sizeof(in));
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
memset(instack,0,sizeof(instack));
memset(scc,0,sizeof(scc));
memset(sccsum,-1,sizeof(sccsum));
while(S.size()) S.pop();
}
void Tarjan(int x){
low[x] = dfn[x] = tot++;
vis[x] = instack[x] = 1;
S.push(x);
for(int i=0 ;i<G1[x].size();i++){
int v = G1[x][i];
if(!vis[v]){
Tarjan(v);
low[x] = min(low[x],low[v]);
}
else if(instack[v]){
low[x] = min(low[x],dfn[v]);
}
}
if(low[x] == dfn[x]){
int cnt = 0;
while(1){
int t = S.top();
S.pop();
instack[t] = 0;
cnt++;
scc[t] = num;
if(t == x) break;
}
ans[num] = cnt;
num++;
}
}
void dfs(int x){
vis[x] = 1;
sum += ans[x];
for(int i=0 ;i<G2[x].size() ;i++){
if(!vis[G2[x][i]])
dfs(G2[x][i]);
}
}
int main(){
int T,count=1;
scanf("%d",&T);
while(T--){
int m;
scanf("%d%d",&n,&m);
init();
while(m--){
int x,y;
scanf("%d%d",&x,&y);
G1[x].push_back(y);
}
for(int i=0 ;i<n ;i++){
if(!vis[i]){
Tarjan(i);
}
}
for(int i=0 ;i<n ;i++){
for(int j=0;j<G1[i].size();j++){
if(scc[i] != scc[G1[i][j]]){
in[scc[i]]++;
G2[scc[G1[i][j]]].push_back(scc[i]);
}
}
}
int res = -1;
for(int i=0 ;i<num ;i++){
if(!in[i]){
sum = 0;
memset(vis,0,sizeof(vis));
dfs(i);
sccsum[i] = sum;
if(sum > res){
res = sum;
}
}
}
printf("Case %d: %d\n",count++,res-1);
bool flag=true;
for(int i=0 ;i<n ;i++){
if(sccsum[scc[i]] == res){
if(flag)
printf("%d",i),flag=false;
else printf(" %d",i);
}
}
printf("\n");
}
return 0;
}