Week8：班长竞选——强连通分量

题目大意
大学班级选班长，N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适。勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？

输入格式
本题有多组数据。第一行 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

题目分析
首先解释一下强连通分量的定义：

在有向图G中，如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。
如果有向图G的每两个顶点都强连通，称G是一个强连通图。
有向图的极大强连通子图，称为强连通分量(strongly connected components)。

对于这道题目，我们可以注意到这一句话：

意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适。

所以，这道题所对应的图，不是强连通图，但是其中是一定有强连通分量的。

那么怎么获得这个图中的所有强连通分量呢？介绍一下Kosaraju算法：

对于上图，我们可以根据强连通分量的定义知道一下这三个强连通分量：

• {1,2,3}
• {4,5,6,7}
• {8}

Kosaraju算法的步骤：

• 使用dfs，确定图中的逆后续序列，对于此图即为4 7 6 5 1 2 3 8（逆后续序列并不唯一，此序列是把点1作为dfs起始点得到的）
• 再dfs一次：按照上面得到的逆后续序列，在原图的反图中进行遍历，每次遍历得到的点即为一个强连通分量。
• 反图就是原图的所有边反向。
• 注意：dfs时记得标记visit数组。

解题思路
把这道题图中所有的强连通分量(SCC)缩成点获得一个新的，由SCC形成的图，那么由于题目中描述的“票可以传递”，那么对于某一个SCC中的点得到的票数就有：

• 当前SCC中的点的数量减一(自己当然不能给自己投票)
• 在SCC的缩点图中，所有具有通向此SCC的有向边的SCC中的点的数量之和。

即对于某一个SCC[i],其中的点的票数为：SCC[i] - 1 + sum( SCC[j] )，其中j可到达i。
除此之外，稍加思考，可以发现最后答案一定出现在出度为 0 的 SCC
中，因此我们将边反向，对每个入度为 0 的点进行 dfs ，计算其能到达的点的 sum( SCC[j] )，即可得到答案。

所以这道题最大的困难其实是一遍遍dfs和一幅幅图~

给出代码：

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 5005;
using namespace std;

int n, m;
vector<int>G1[N], G2[N], Gx[N];//正向，反向，缩点图
int dcnt, scnt;
int dfn[N], c[N];
int scc[N];//某一scnt里点的个数
int sccvis[N];//某一scnt是否遍历到
int s_deg[N];//度

int vis[N];

int maxgrade;
vector<int>winner;

void Init()
{
	for (int i = 0; i < N; i++)
	{
		G1[i].clear();
		G2[i].clear();
		Gx[i].clear();
	}

	winner.clear();
	memset(vis, 0, sizeof vis);
	memset(dfn, 0, sizeof dfn);
	memset(c, 0, sizeof c);
	memset(scc, 0, sizeof scc);
	memset(s_deg, 0, sizeof s_deg);
	dcnt = 0;
	scnt = 0;
	maxgrade = 0;
}

void dfs1(int x)
{
	vis[x] = 1;
	for (auto y : G1[x])
	{
		if (!vis[y]) dfs1(y);
	}
	dfn[++dcnt] = x;
}

void dfs2(int x)
{
	c[x] = scnt;
	scc[scnt]++;
	for (auto y : G2[x])
	{
		if (!c[y]) dfs2(y);
	}
}

void dfsx(int x, int& grade)
{
	sccvis[x] = 1;
	for (auto y : Gx[x])
	{
		if (!sccvis[y])
		{
			grade += scc[y];
			dfsx(y, grade);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	int casenum = 0;
	while (t--)
	{
		Init();

		cin >> n >> m;
		for (int i = 0, a, b; i < m; i++)
		{
			cin >> a >> b;
			G1[a + 1].push_back(b + 1);
			G2[b + 1].push_back(a + 1);
		}

		for (int i = 1; i <= n; i++)
		{
			if (!vis[i]) dfs1(i);
		}

		for (int i = n; i >= 1; i--)
		{
			if (!c[dfn[i]])
			{
				++scnt;
				dfs2(dfn[i]);
			}
		}

		for (int i = 1; i <= n; i++)
		{
			for (auto y : G1[i])
			{
				if (c[i] == c[y]) continue;
				
				Gx[c[y]].push_back(c[i]);//保存反图
				s_deg[c[i]]++;
			}
		}

		for (int i = 1; i <= scnt; i++)
		{
			if (!s_deg[i])//入度为0
			{
				int the_ans = scc[i] - 1;
				memset(sccvis, 0, sizeof sccvis);
				dfsx(i, the_ans);

				if (the_ans > maxgrade)
				{
					winner.clear();
				}
				if (the_ans >= maxgrade)
				{
					for (int j = 1; j <= n; j++)
					{
						if (c[j] == i)
						{
							winner.push_back(j - 1);
						}
					}
					maxgrade = the_ans;
				}
			}
		}

		sort(winner.begin(), winner.end());

		cout << "Case " << ++casenum << ": " << maxgrade << endl;
		for (int i = 0; i < winner.size(); i++)
		{
			if (i == winner.size() - 1)
			{
				cout << winner[i] << endl;
			}
			else
			{
				cout << winner[i] << ' ';
			}
		}
	}
}