week8-C(强连通子图）班长竞选

题意

大学班级选班长，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开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

样例：
input:
2
4 3
3 2
2 0
2 1

3 3
1 0
2 1
0 2
output:
Case 1: 2
0 1
Case 2: 2
0 1 2

思路

• 由于投票的传递性，我们此时考虑SCC并且缩点；
• 缩点以后我们就可以发现，对于第i个点的SCC来说，它的票数分为两部分：
  1. SCC[i]-1,身处SCC中其他的点；
  2. 其他SCC中的点，sum(SCC[j]), j是可以到达i的
• 这是一个有向图：
  
  对于这个有向图，得票最多是应该出度为0的，但是我们不便通过这个有向图进行求取其他的SCC中点的个数，我们可以在缩点的时候顺便求出反图，如下图
  
  此时我们就可以用dfs进行遍历，求出其他遍历到的SCC的点的个数总和
• 所有入度为0的点都应该进行dfs,然后得到票数，存储在一个数组num1里面，进行排序，输出最大票数，同时也要输出所有的得票最高者（升序）；

总结

• SCC编号是由逆后序序列dfs生成的，缩点的时候可以直接生成反图；
• num数组用来记录每一个SCC中点的个数
• 需要额外定义一个数组num1，来存储缩点以后的图中入度为0的点的票数，然后进行排序，目的是为了得出最高的票数，及其SCC编号
• 胜者不止一个，所以要将数组num1排序后最大的所有人全部找出来；且注意，这些人编号是从小到大的，需要进行排序

int max_number = num1[coutn - 1].sum;
	int cot = 0;//记录最高票数的人
	for (int i = coutn - 1; i >= 0; i--)
	{
		if (num1[i].sum == max_number)   //从大到小每一个SCC的票数与最高票数进行比较，如果相等，存入数组
		{
			for (int j = 0; j < N; j++)//存储每一个人
			{
				if (c[j] == num1[i].scn)
					max_n[cot++] = j;
			}
		}
	}
	//排序输出最高票数的人
	sort(max_n, max_n + cot);
	for (int i = 0; i < cot-1; i++)
		cout << max_n[i] << " ";
	cout << max_n[cot - 1];

错误总结

忽略行末空格

for (int i = 0; i < cot-1; i++)
		cout << max_n[i] << " ";
	cout << max_n[cot - 1];

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct numbc
{//存储入度为0的人的票数
	int number;
	int scn;//scc编号
	int sum;//scc票数
	bool operator<(const numbc& n)
	{
		return sum < n.sum;
	}
}num[5010],num1[5010];//进行存储每一个入度为0的人的票数

int dfn[5010], vis[5010], c[5010], dcnt, scnt;   
//dfn为后序的序列，vis为标记数组，c为SCC数组，dcnt为后序遍寻参数，scnt为SCC遍寻参数
vector<int> G[5010]; //原图
vector<int> G1[5010];  //反图
vector<int> G2[5010];  //缩点之后的反图
int max_n[5010];//记录最高票数的所有人
int in_deg[5010];//记录入度
int sum = 0;//进行求取票数
void init(int N)
{//初始化图的存储
	for (int i = 0; i <= N; i++)
	{
		G[i].clear();
		G1[i].clear();
		G2[i].clear();
		
	}
	memset(dfn, 0, sizeof dfn);
}

void dfs1(int x)
{//第一次dfs进行求后序序列
	vis[x] = 1;
	for (int i = 0; i < G[x].size(); i++)
		if (vis[G[x][i]] == 0)
			dfs1(G[x][i]);
	dfn[++dcnt] = x;
}
void dfs2(int x)
{//第二次dfs求SCC及其编号
	c[x] = scnt;
	num[scnt].number++;
	for (int i = 0; i < G1[x].size(); i++)
		if (c[G1[x][i]] == 0)
			dfs2(G1[x][i]);
}
void dfs3(int x)
{//第三次dfs求票数
	vis[x] = 1;
	//sum = sum + num[x];
	for (int i = 0; i < G2[x].size(); i++)
		if (vis[G2[x][i]] == 0) {
			sum = sum + num[G2[x][i]].number;
			dfs3(G2[x][i]);
		}
			
}
void suodian(int N)
{//SCC缩点
	for (int i = 0; i <N; i++)
	{
		for (int j = 0; j < G[i].size(); j++) 
		{
			int temp = G[i][j];
			if (c[i] == c[temp])
				continue;
			else {
				G2[c[temp]].push_back(c[i]);  //直接调成反图
				in_deg[c[i]]++;  //入度加一
			}
		}
	}
}
void kosaraju(int N) //进行求SCC
{
	//初始化
	dcnt = 0;     
	scnt = 0;
	memset(vis, 0, sizeof vis);
	memset(c, 0, sizeof c);
	for (int i = 0; i < 5010; i++)
	{
		num[i].number = 0;
		num[i].scn = 0;
		num[i].sum = 0;
		num1[i].number = 0;
		num1[i].scn = 0;
		num1[i].sum = 0;
	}
	memset(in_deg, 0, sizeof in_deg);


	//第一遍dfs求出后序序列
	for (int i = 0; i <= N; i++)
		if (vis[i] == 0)
			dfs1(i);
	//第二次dfs按照逆后序序列进行，求出SCC的编号
	for (int i = N; i >= 0; i--)
		if (c[dfn[i]] == 0)
		{
			++scnt;
			dfs2(dfn[i]);
		}
	
	suodian(N);//进行SCC缩点

	//第三次dfs进行求取入度为0的点的票数
	memset(max_n, 0, sizeof max_n);
	sum = 0;//记录票数

	int coutn = 0;//记录入度为0的人的票数
	for (int i = 1; i <= scnt; i++)
	{//求每一个入度为0的点的票数
		if (in_deg[i] == 0) {
			sum = num[i].number - 1;
			memset(vis, 0, sizeof vis);
			dfs3(i);
			//将其存储在一个数组里面进行排序
			num1[coutn].scn = i;
			num1[coutn].sum = sum;
			coutn++;
			
		}
	}
	sort(num1, num1 + coutn);
	cout << num1[coutn-1].sum << endl;//输出最高票数
	//输出所有的最高票数的人
	int max_number = num1[coutn - 1].sum;
	int cot = 0;//记录最高票数的人
	for (int i = coutn - 1; i >= 0; i--)
	{
		if (num1[i].sum == max_number)   //从大到小每一个人与最高票数进行比较，如果相等，存入数组
		{
			for (int j = 0; j < N; j++)
			{
				if (c[j] == num1[i].scn)
					max_n[cot++] = j;
			}
		}
	}
	//排序输出最高票数的人
	sort(max_n, max_n + cot);
	for (int i = 0; i < cot-1; i++)
		cout << max_n[i] << " ";
	cout << max_n[cot - 1];
	cout << endl;
}
int main()
{
	int number;
	cin >> number;
	int count = 1;
	for (int i = 0; i < number; i++)
	{
		int N, M;
		scanf("%d%d", &N, &M);
		init(N);
		for (int i = 0; i < M; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			G[x].push_back(y);  //原图
			G1[y].push_back(x); //反图

		}
		cout << "Case " << count << ": ";	
		kosaraju(N);
		count++;
	}
	return 0;
}