程序设计思维 C - 班长竞选 （强连通分量、kosaraju算法）
题目
大学班级选班长，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
思路
一、强连通分量（SCC）
强连通分量的概念：
来源：刘建东学长、黄瑞哲学长的ppt
二、kosaraju算法
kosaraju算法是一种求强连通分量的算法。
1.原图和反图
来源：刘建东学长、黄瑞哲学长的ppt
2.kosaraju算法
（1）用DFS在原图找逆后序序列
（2）用DFS在反图中按照逆后序序列遍历，每次由起点遍历到的点即构成一个强连通分量
三、解题
1.构建图
如果A认为B合适，则构建一条从A到B的边（A, B）。
2.求出图的强连通分量
使用kosaraju算法求出图的强连通分量。
3.缩点、求解
SCC[i]：第i个强连通分量中的点的数目
若有一条从第j个强连通分量到第i个强连通分量的边（即第j个强连通分量可达第i个强连通分量），则说明第j个“团体”的同学认为第i个“团体”的同学合适。
故设X在第i个强连通分量中，则认为X合适人数有：
SCC[i] - 1 + sum(SCC[j])，第j个强连通分量可达第i个强连通分量
不难理解，得票最多的同学一定在出度为0的强连通分量中。
故在反图中对每个入度为0的点进行DFS，计算其能到达的点的SUM(SCC[j])，即可得到答案。
代码
#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#define MAX_V 5050
using namespace std;
int T;
int N, M;
int A, B;
vector<int> G1[MAX_V]; // 原图
vector<int> G2[MAX_V]; // 反图
vector<int> SCC[MAX_V]; // 缩点后的图
int dfn[MAX_V]; // 逆后序序列
int vis[MAX_V];
int c[MAX_V]; // c[i]：第i个顶点所在的连通分量（的编号）
int dcnt; // 逆后序序列计数
int scnt; // 连通分量计数
int vNum[MAX_V]; // vNum[i]：第i个连通分量中的顶点数
int Max; // 记录最大的点数
int cnt;
vector<int> v;
set<int> s[MAX_V];
void dfs1(int x) { // 在原图找逆后序序列
vis[x] = 1;
for (int i = 0; i < G1[x].size(); i++)
if (!vis[G1[x][i]]) dfs1(G1[x][i]);
dfn[++dcnt] = x;
}
void dfs2(int x) { // 在反图中按照逆后序序列遍历
c[x] = scnt;
vNum[scnt]++;
for (int i = 0; i < G2[x].size(); i++) {
if (!c[G2[x][i]]) dfs2(G2[x][i]);
}
}
void kosaraju()
{
for (int i = 0; i < N; i++)
if (!vis[i]) dfs1(i);
for (int i = N - 1; i >= 0; i--)
if (c[dfn[i]] == 0) {
scnt++;
dfs2(dfn[i]);
}
}
void shrink()
{
for (int i = 0; i < N; i++)
for (int j = 0; j < G1[i].size(); j++)
if (c[i] != c[G1[i][j]]) {
SCC[c[i]].push_back(c[G1[i][j]]);
s[c[G1[i][j]]].insert(c[i]);
}
}
void dfs(int x) {
vis[x] = 1;
cnt += vNum[x];
for (set<int>::iterator it = s[x].begin(); it != s[x].end(); it++)
if (!vis[*it]) dfs(*it);
}
//void print()
//{
// for (int i = 1; i <= scnt; i++) {
// if (!SCC[i].size()) {
// cnt = 0;
//
// memset(vis, 0, sizeof(vis));
//
// dfs(i);
//
// if (cnt > Max) {
// Max = cnt;
// v.clear();
// v.push_back(i);
// }
// else if (cnt == Max)
// v.push_back(i);
// }
// }
//
// Max--;
// cout << Max << endl;
//
// bool end = false;
// for (int j = 0; j < N; j++)
// for (int k = 0; k < v.size(); k++)
// if (c[j] == v[k]) {
// if (!end) end = true;
// else cout << " ";
// cout << j;
// }
//
// cout << endl;
//}
void init()
{
memset(dfn, 0, sizeof(dfn));
memset(vis, 0, sizeof(vis));
memset(c, 0, sizeof(c));
memset(vNum, 0, sizeof(vNum));
v.clear();
for (int i = 0; i < N; i++) {
G1[i].clear();
G2[i].clear();
SCC[i].clear();
s[i].clear();
}
scnt = 0;
dcnt = 0;
Max = 0;
}
int main() {
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> N >> M;
init();
for (int i = 0; i < M; i++) {
cin >> A >> B;
G1[A].push_back(B);
G2[B].push_back(A);
}
kosaraju();
shrink();
cout << "Case " << t << ":" << " ";
for (int i = 1; i <= scnt; i++) {
if (!SCC[i].size()) {
cnt = 0;
memset(vis, 0, sizeof(vis));
dfs(i);
if (cnt > Max) {
Max = cnt;
v.clear();
v.push_back(i);
}
else if (cnt == Max)
v.push_back(i);
}
}
Max--;
cout << Max << endl;
bool end = false;
for (int j = 0; j < N; j++)
for (int k = 0; k < v.size(); k++)
if (c[j] == v[k]) {
if (!end) end = true;
else cout << " ";
cout << j;
}
cout << endl;
}
return 0;
}