算法
强连通分量
题目描述
N个同学竞选班长并发表意见，意见即为A认为B合适，且意见具有传递性（即A认为B、B认为C，则A也认为C合适）。现要求求出得票最多的人（可能多个）。
解题思路
由于题目中并没有说意见的传递不能构成环，则在整个图中可能存在强连通分量（即每两点都互相认为合适），如此将无法直接求解。
首先将图中强连通分量求出，将一个联通分量视为一个有多票的点（即进行缩点），如此图中将不会再有互相认为合适的点，使用dfs求解即可。
由于使用邻接表，判断“谁可到达此点”不易于寻找，则在反向图中使用dfs寻找“此点可到达谁”以达到同样的效过。
可以证明，若得票最多则该点（缩点后的点）必然出度为0。
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int Maxn = 5010;
const int Maxm = 30010;
struct At {
int x, y, next;
} e[2][Maxm];
int h[2][Maxn];
void makeE(int x, int y, int cnt, int opt) {
e[opt][cnt].x = x;
e[opt][cnt].y = y;
e[opt][cnt].next = h[opt][x];
h[opt][x] = cnt;
}
bool vis[Maxn];
int dfn[Maxn], bel[Maxn];
int dcnt, scnt;
int n, m;
void dfs1(int x) {
vis[x] = 1;
for (int i = h[0][x]; i > 0; i = e[0][i].next)
if (!vis[e[0][i].y]) dfs1(e[0][i].y);
dfn[++dcnt] = x;
}
void dfs2(int x) {
bel[x] = scnt;
for (int i = h[1][x]; i > 0; i = e[1][i].next)
if (!bel[e[1][i].y]) dfs2(e[1][i].y);
}
void kosaraju() {
dcnt = scnt = 0;
memset(vis, 0, sizeof(vis));
memset(bel, 0, sizeof(bel));
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; i--)
if (!bel[dfn[i]]) {
scnt++;
dfs2(dfn[i]);
}
return;
}
int du[Maxn];
int scc[Maxn];
int ans[Maxn];
int dfs(int x) {
vis[x] = 1;
//if (ans[x]) return ans[x];
ans[x] = scc[x];
for (int i = h[0][x]; i > 0; i = e[0][i].next) {
int y = e[0][i].y;
if (!vis[y]) {
ans[x] += dfs(y);
}
}
return ans[x];
}
int main() {
int tt;
cin >> tt;
for (int t = 1; t <= tt; t++) {
cin >> n >> m;
int a, b;
//int cnt=0;
memset(h, 0, sizeof(h));
for (int i = 1; i <= m; i++) {
cin >> a >> b;
a++, b++;
makeE(a, b, i, 0);
makeE(b, a, i, 1);
}
kosaraju();
memset(du, 0, sizeof(du));
memset(scc, 0, sizeof(scc));
for (int i = 1; i <= m; i++) {
int x = e[0][i].x, y = e[0][i].y;
if (bel[x] != bel[y]) {
du[bel[x]]++;
}
}
for (int i = 1; i <= n; i++) {
scc[bel[i]]++;
}
//缩点并计算
int socer = 0;
memset(ans, 0, sizeof(ans));
memset(h, 0, sizeof(h));
for (int i = 1; i <= m; i++) {
makeE(bel[e[1][i].x], bel[e[1][i].y], i, 0);
}
for (int i = 1; i <= scnt; i++) {
if (du[i] == 0) {
memset(vis, 0, sizeof(vis));
ans[i] = dfs(i);
socer = max(socer, ans[i]);
}
}
printf("Case %d: %d\n", t, socer - 1);
int prt = -1;
for (int i = 1; i <= n; i++) {
if (ans[bel[i]] == socer) {
if (prt != -1) {
printf("%d ", prt-1);
}
prt = i;
}
}
printf("%d\n", prt-1);
}
return 0;
}
/*
1
8 11
0 2
0 3
1 0
2 1
2 6
3 4
4 5
5 6
6 3
7 2
7 6
ans:7
3 4 5 6
1
8 11
0 1
1 2
2 0
2 7
6 7
6 2
3 0
3 6
4 3
5 4
6 5
ans:7
7
1
7 9
1 2 2 3 3 1
4 5 5 6 6 4
4 2
5 3
0 5
*/
题目总结
注意求解强连通分量后必须进行缩点，自行更改dfs达到缩点的效过大概率出错。
注意在dfs算分值时，不要使用记忆化记录经过节点的得票，因为该得票的统计并不完全。
题目原文
大学班级选班长，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
