本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。
对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。
接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！
样例数据：
输入：
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2输出：
Case 1: 2
0 1
Case 2: 2
0 1 2可供参考的另一个样例图：
（这个算法真的超级麻烦，要实现的东西超级多，所以从模板开始一点一点写）
经过分析可以知道，即能到达某一点的前面的点数最多的这个点，即为的票数最多的人。将图反向即可得到，这个点能到达的点的数量一定是最多的。同时图中可以存在环路，即有强连通分量。易知，这个点能到达的所有连通分量的点的和（自己所在的连通分量的点数需要减1，因为自己不能给自己投票）。即转化为先求图中的连通分量。然后开始跑反图，记录能到达的所有的连通分量的点的数量的和。
跑出连通分量：
两遍dfs跑出连通分量，其中逆后序序列很重要，第一遍在原图中跑出逆后序序列，模板如下：
跑出逆后序序列后，在反图中按照逆后序序列进行遍历，抛出scc，每次由起点遍历到的每个点在一构成一个scc。
代码模板：
随后将scc进行缩点，记录下每个scc的点数和入度，容易票数最多的人一定在入度为0的scc中。
即以入度为0的scc在反图中往回跑，记录下能到达的所有的scc，并将点数全部加上。
缩点代码：
最后输出点数最多的,以及这个scc中所有的点。
总结：
其中要实现很多东西，比如后序逆序列，scc，还有缩点，缩点怎么缩，以及缩以后还要知道入度，也要反向遍历，以及缩点后的遍历入度为零的点，入度为零的点可能不止一个，其点的数量大小可能相同又可能不同，该记录下什么参数，最后将这些点输出来。在这个算法里，光是dfs就跑了很多次，每次的作用又不同，以及不断在正图和反图中来回切换的跑，又一次感受到菜鸡的难处。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <set>
using namespace std;
int T, N, M, A, B;
int f[5010], f1[5010], vis[5010], c[5010], fcnt; //后序序列， ,标记，点在连通分量的标记 后续的下标
vector<int> G[5010], G1[5010], G2[5010]; //分别为原图，反图和缩点后的图
int cnt, Cnt[5010]; //scc的个数 ， 连通分量中的点数
int Msum, tsum; //记录最大的点数
vector<int> Mcnt; //存放点数最大的连通分量的序号
set<int> SET[5010]; //缩点的时候,set可以过滤
void dfs1(int x) { //确定原图的逆后序序列
vis[x] = 1;
for (unsigned int i = 0; i < G[x].size(); i++) {
if (!vis[G[x][i]]) dfs1(G[x][i]);
}
f[x] = fcnt++;
}
void dfs2(int x) { //跑连通分量
c[x] = cnt; //记录点所在的连通分量的序号
Cnt[cnt]++; //记录连通分量中的点的数量
for (unsigned int i = 0; i < G1[x].size(); i++) {
if (!c[G1[x][i]]) dfs2(G1[x][i]);
}
}
void dfs3(int x) { //缩点后的图的遍历
vis[x] = 1;
tsum += Cnt[x];
set<int>::iterator it;
for (it = SET[x].begin(); it != SET[x].end(); it++) {
if (!vis[*it]) dfs3(*it);
}
}
//缩点求解
void solve() {
for (int i = 0; i < N; i++) { //缩点
for (unsigned int j = 0; j < G[i].size(); j++) {
if (c[i] == c[G[i][j]]) {
continue;
}
else {
G2[c[i]].push_back(c[G[i][j]]); //缩点后正常的图，为判断入度
SET[c[G[i][j]]].insert(c[i]);//过滤后的图，缩点后的图遍历得到点数
}
}
}
for (int i = 1; i <= cnt; i++) { //查找入度为零的连通分量
if (!G2[i].size()) { //连通分量为0，则遍历，得到点数
tsum = 0;
memset(vis, 0, sizeof(vis));
dfs3(i);
if (tsum > Msum) { //因为入度为零的点可能不止一个，记录连通分量序号
Msum = tsum;
Mcnt.clear();
Mcnt.push_back(i);
}
else if (tsum == Msum) {
Mcnt.push_back(i);
}
}
}
int tmp = 0;
cout << Msum - 1 << endl; //输出票数
for (int j = 0; j < N; j++) { //输出点的序号
for (unsigned int l = 0; l < Mcnt.size(); l++) {
if (c[j] == Mcnt[l]) {
if (tmp == 0) {
tmp = 1;
}
else {
cout << " ";
}
cout << j ;
}
}
}
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin >> T;
for (int k = 0; k < T; k++) {
cin >> N >> M; //N个同学 ，M个关系
//初始化
memset(f, 0, sizeof(f));
memset(f1, 0, sizeof(f1));
memset(vis, 0, sizeof(vis));
memset(c, 0, sizeof(c));
memset(Cnt, 0, sizeof(Cnt));
fcnt = 0, cnt = 0, Msum = 0;
for (int i = 0; i < N; i++) {
G[i].clear(); G1[i].clear(); G2[i].clear(); SET[i].clear();
}
Mcnt.clear();
for (int i = 0; i < M; i++) {
cin >> A >> B;
G[A].push_back(B); //原图
G1[B].push_back(A); //反图
}
for (int i = 0; i < N; i++) {
if (!vis[i]) dfs1(i);
}
for (int i = 0; i < N; i++) { //得到后序序列
f1[f[i]] = i;
}
for (int i = N - 1; i >= 0; i--) {
if (c[f1[i]] == 0) {
cnt++;
dfs2(f1[i]);
}
}
cout << "Case " << k + 1 << ":" << " ";
solve();
}
return 0;
}