[week8]班长竞选——强连通分量
题意
大学班级选班长，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开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！
输入样例
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. 什么是强连通分量？
强连通指的是一个从任意点可以到达任意点的有向图，即任意两点连通。强连通分量指的就是强连通子图。
上图中红框中的子图即为强连通子图。
2. DFS序
DFS序是指的利用DFS搜索法在强连通图中所得到的三种不同序列：
- 前序序列
- 后序序列
- 逆后序序列
这个和树结构中的前后序有些不太一样。其中逆后序序列就是后序序列的反置。
DFS序中的前序和后序序列正是通过DFS法的递归来实现的。
（1） 前序标记
前序就是在最开始递归调用的过程中，根据调用层数来标记。如，
进入递归函数 —— 当前遍历点 —— 标记为1
调用递归函数第1次 —— 当前遍历点 —— 标记为2
调用递归函数第2次 —— 当前遍历点—— 标记为3
…
（2） 后序标记
而后序就是在递归调用到达边界后回溯的过程中，根据回溯的层数（从下至上）来标记。如，
到达递归边界，从当前开始回溯 —— 当前遍历点—— 标记为1
回溯第二层 —— 当前遍历点 —— 标记为2
回溯第三层 —— 当前遍历点 —— 标记为3
…
????求DFS序代码模版
- kosaraju算法
该算法是针对求解强连通分量的。通常利用这个算法将有向图中的所有强连通分量找到。
算法步骤：
- 用DFS求出原图中的逆后序序列
- 用DFS根据逆后序序列遍历反图，标记每个起点和它可以到达的点为同一强连通分量
【小tip：反图就是将原图中所有边反向所得到的图。】
????kosaraju算法代码模版
- 题目分析
根据题目可知，题目给出的数据模型一定是一个有向图。
题目要求求出得票最多的同学。经过分析可以发现，票数具有传递性，那么实际上就是要求出所有点，满足直接或间接指向这些点的点数最大。
转换为图中的特征，也就是求出指向它的连通点数最多的所有点。
这就是为什么想到了会出现强连通分量。
不论该有向图中是否存在强连通分量，我们都可以将一个有向图分为几个强连通分量连接的图结构。一个点同样可以化为一个强连通分量。
一个点所在强连通分量中除去自己以外的所有都直接或间接指向它。显然，指向这个点所在强连通分量的强连通分量中的所有点也是间接指向这个点的。
如果要一个点指向它的连通点最多，最好的情况就是这个点所在的强连通分量不指向任何点，只有入度没有出度。那么，答案就自然是在那些出度为0的强连通分量里的。
那么对这些出度为0的强连通分量进行搜索，找到所有与它相连的强连通分量，那么其中的点所得的票数就能求出来啦。
-
优化&问题
-
重复利用数组空间
从开始写这个代码，就会发现在不断的新增数组来存储数据。我的心情是害怕的，因此我想尽办法重复利用那些不再会被使用的数据所在的容器，来存储之后的数据。
- 答案序号升序输出
最开始交了好几次都是WA，但是代码确实也找不到什么问题【debug了好久才理清这么多步骤】。最后我猜想可能是这个原因。最后我改了存储答案的方式并按升序输出之后就AC了????????♂️
总结
- 强连通分量问题涉及的算法和求解步骤真的有点多。首先要理解这些算法原理，然后再耐心地一步步写。其中会用到许多数组和变量，需要反复的调试才能保证不混乱⚠️
代码
//
// main.cpp
// lab3
//
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
vector<int> Pic[5010],Rev[5010]; //正反图
bool vis[5010],vis3[5010]; //分别标记第一次dfs到达点、第三次dfs到达scc和点
int times2,sign,scc[5010],result,scc_num[5010],order[5010],n = 0;
void dfs1(int a) //深搜标记当前点能到达的所有点
{
vis[a] = 1; //标记当前点为已到达
for( int i = 0 ; i < Pic[a].size() ; i++ )
{
if( !vis[Pic[a][i]] )
dfs1(Pic[a][i]);
}
order[n - (++times2)] = a; //递归回溯是标记后序序列，直接逆序放入数组(从数组第0位开始放）
}
void dfs2(int a) //在反图中深搜找到所有scc
{
scc[a] = sign; //将当前到达点的标记为num，代表其所在scc标号
scc_num[sign]++; //当前scc对应点数+1
for( int i = 0 ; i < Rev[a].size() ; i++ )
{
if( scc[Rev[a][i]] == -1 ) //如果当前连接点没有标记对应的scc编号，进行遍历
dfs2(Rev[a][i]);
}
}
void dfs3(int a) //找到标号为a的scc在反向缩点图中能到达的所有scc
{
//求入度为0的选手的总票数 = 自己所在scc中点数 + 所在scc能到达的scc的点总数 - 1
result += scc_num[a]; //当前遍历的scc一定是之前没遍历过的，因此票数直接累加当前遍历scc中的点数
vis3[a] = 1; //将当前scc标记为已遍历
for( int i = 0 ; i < Pic[a].size() ; i++ ) //遍历当前scc在反向缩点图中邻接的所有scc
{
if( !vis3[Pic[a][i]] ) //只遍历那些还没有访问过的邻接scc
dfs3(Pic[a][i]);
}
}
int main()
{
ios::sync_with_stdio(false);
int t = 0,m = 0,a = 0,b = 0;
scanf("%d",&t);
for( int k = 1 ; k <= t ; k++ )
{
scanf("%d %d",&n,&m);
while( m-- )
{
scanf("%d %d",&a,&b);
Pic[a].push_back(b); //原图
Rev[b].push_back(a); //反向图
}
times2 = 0; //后序序列标记
sign = 0; //记录scc编号
result = -1; //记录被选点的票数
for( int i = 0 ; i < n ; i++ )
{
vis[i] = 0;
scc[i] = -1; //存储点i的scc编号
vis3[i] = 0;
order[i] = 0; //存储该图的逆后序序列（第i个点为order[i]）
scc_num[i] = 0; //存储每个scc中的点数
}
for( int i = 0 ; i < n ; i++ ) //标记强连通中所有点，得到逆后序序列
{
if( !vis[i] )
dfs1(i);
}
for( int i = 0 ; i < n ; i++ ) //依次遍历逆后序序列，标记所有scc
{
if( scc[order[i]] == -1 ) //若当前点不属于任何scc
{
sign++; //scc标号+1（标号从1开始算起）
scc_num[sign] = 0; //记录当前scc中点的个数
dfs2(order[i]);
}
Pic[i].clear(); //将原图清空用于装scc的反向缩点图
vis[i] = 0; //重新初始化访问数组，用于之后标记在反向图中有入度的scc
order[i] = 0; //清空序列数组，为了最后给得票最高选手排序
}
//记录所有互相连通的scc（反向图）
//scc反向缩点图
for( int i = 0 ; i < n ; i++ ) //遍历反向图所有点
{
if( !Rev[i].empty() ) //如果当前点i有邻接点
{
for( int j = 0 ; j < Rev[i].size() ; j++ ) //遍历点i的所有邻接点
{
int to = Rev[i][j]; //当前邻接点
//若其邻接点和它不在一个scc中，说明这两个scc连通
//该点所在scc指向其邻接点所在scc（反向图）
if( scc[to] != scc[i] )
{
//存入的是scc编号，i所在scc邻接Rev[i][j]所在的scc
Pic[scc[i]].push_back(scc[to]); //scc[i]指向scc[rev[i][j]]
vis[scc[to]] = 1; //邻接点所在scc有入度，进行标记
}
}
}
}
int max = 0,sign2 = 0; //用于记录最高票数;索引，用于存储所有被选点
//反向图中入度为0的scc一定是原图中出度为0的scc
//得票最多的选手一定在这样的scc中
for( int i = 1 ; i <= sign ; i++ ) //遍历所有scc
{
if( vis[i] == 0 ) //若当前scc在反向图中入度为0
{
for( int j = 0 ; j < n ; j++ ) //遍历所有图中所有点，找到在该scc中的点
{
if( scc[j] != i ) //若点不在该scc中则跳过
continue;
for( int i = 1 ; i <= sign ; i++ ) //初始化，用于标记dfs中已经计算过的scc
vis3[i] = 0;
result = -1; //票数初始化，先减去自身的一票
dfs3(i); //深搜找到该scc能到达的所有scc，得到当前选手的票数
if( result > max ) //如果当前答案大于之前的最高票数
{
sign2 = 0; //则之前记录的所有点作废
order[sign2++] = j; //将j从头开始放入数组中
max = result; //更新最高票数
}
else if( result == max ) //若当前点票数等于最高票数
order[sign2++] = j; //接着上次依次放入数组中
else //否则直接略过
continue;
}
}
}
cout<<"Case "<<k<<": "<<max<<endl; //输出最高票数
sort(order,order + sign2); //sign最后就等于选出的点数
for( int i = 0 ; i < sign2 ; i++ ) //输出所有选手
{
printf("%d",order[i]);
if( i < sign2 - 1 )
printf(" ");
}
printf("\n");
for( int i = 0 ; i < n ; i ++ ) //清空正反向图
{
Pic[i].clear();
Rev[i].clear();
}
}
return 0;
}