WEEK8 周记 作业——kosaraju模拟&DFS序_班长竞选

一、题意

1.简述

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

2.输入格式

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。

3.输出格式

对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

4.样例

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

二、算法

主要思路

先利用kosaraju模拟求出所有的SCC（强连通子图）。然后将每一子图缩成一个点，形成一个缩点图。

这个题主要在于思路，代码实际上并不难写，主要是通过多次dfs实现的。

---

需要注意的是，memset这种函数有可能会造成超时，因为我们实际上并不需要清空全部数组，只需要清空数组中的1到n或0到n。

---

三、代码

#include<iostream>
#include<cstring>
#include<algorithm> 
#include<string>
#include<cstdlib>
#include<queue>
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
struct edge{
	int to,next;
} ed1[30010],ed2[30010],eds[30010],edsf[30010];
int head1[5010],head2[5010],heads[5010],headsf[5010];
int num_edge = 0;

int vis[5010];
int c[5010];
int seq[5010];//不需要每组都清空，只需要将num_seq设为0即可 
int scnt = 0;
int num_seq = 0;
int sum[5010];

void add(int from,int to,edge ed[],int head[]){
	ed[++num_edge].next = head[from];
	head[from] = num_edge;
	ed[num_edge].to = to;
}
void dfs_seq(int s){
	vis[s] = 1;
	for(int i=head1[s];i;i=ed1[i].next){
		if(!vis[ed1[i].to])
			dfs_seq(ed1[i].to);
	}
	seq[num_seq] = s;
	num_seq++;
}
void dfs2(int s){
	vis[s] = scnt;
	sum[scnt]++;
	for(int i=head2[s];i;i=ed2[i].next){
		if(!vis[ed2[i].to])
			dfs2(ed2[i].to);
	}
}
void dfs3(int s,int& ssum,int flag){
	ssum += sum[s];
	c[s] = flag;
	for(int i=headsf[s];i;i=edsf[i].next){
		if(c[edsf[i].to]!=flag)
			dfs3(edsf[i].to,ssum,flag);
	}
}
 
int main(){
	int t;
	scanf("%d",&t);
	for(int tt=1;tt<=t;tt++){//一定别忘了看看是不是多组数据！
		int n,m;
		scanf("%d%d",&n,&m);
		//mem(vis,0);
		for(int i=0;i<n;i++){
			vis[i] = 0;
			head1[i] = 0;
			head2[i] = 0;
		}
		//mem(head1,0);
		//mem(head2,0);
		
		num_edge = 0;
		int i;
		for(i=0;i<m;i++){//O(m)
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b,ed1,head1);
			num_edge--;
			add(b,a,ed2,head2);
		}
		for(int i=0;i<n;i++)//O(n)
			if(!vis[i]) dfs_seq(i);
		
		for(i=0;i<=n+10;i++){//这里sum重新赋0的时候不能是i<n，因为sum是用的1-scnt的，所以这里应该是[1,n]赋值为0,而不是[1,n) 
			vis[i] = 0;
			sum[i] = 0;	
		}
		num_seq = 0;
		scnt = 0;
		for(i=n-1;i>=0;i--)//对反图进行逆后序遍历 //O(n)
			if(!vis[seq[i]]) scnt++,dfs2(seq[i]);
		
		//用反图缩点,共有scnt个点 //O(m)
		num_edge = 0;
		for(i=0;i<=scnt;i++){
			heads[i] = 0;
			headsf[i] = 0;
		}
		for(i=0;i<n;i++){
			for(int j=head2[i];j;j=ed2[j].next){
				if(vis[i]==vis[ed2[j].to]) continue;
				add(vis[i],vis[ed2[j].to],edsf,headsf);
				num_edge--;
				add(vis[ed2[j].to],vis[i],eds,heads);
			}
		}
		
		//dfs缩点图,点序号从1开始 
		for(i=0;i<=scnt;i++) c[i] = 0;
		int ssum = 0;
		int maxi = 0;
		int smax = 0;
		for(i=1;i<=scnt;i++){
			if(heads[i]==0){//反缩点图中入度为0 
				ssum = 0;
				dfs3(i,ssum,i); 
				if(ssum>smax){
					smax = ssum;
					maxi = i;	
				}
				sum[i] = ssum;
			}
		}
		
		printf("Case %d: ",tt);
		printf("%d\n",smax-1);
		int count = 0;
		for(i=0;i<n;i++){
			if(sum[vis[i]]==smax){
				if(count>0) printf(" ");
				printf("%d",i);
				count++;
			}
		}
		printf("\n");
	}
	return 0;
}