欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 18:10:35
...

题意

大学班级选班长,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的
  • 这是一个有向图:
    week8-C(强连通子图)班长竞选
    对于这个有向图,得票最多是应该出度为0的,但是我们不便通过这个有向图进行求取其他的SCC中点的个数,我们可以在缩点的时候顺便求出反图,如下图
    week8-C(强连通子图)班长竞选
    此时我们就可以用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;
}