班长竞选

竞选"/>

班长竞选

问题描述：

大学班级选班长，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 13 3
1 0
2 1
0 2

样例输出：

Case 1: 2
0 1
Case 2: 2
0 1 2

解题思路：

对于一条数据a给b投票，那么我们就可以将其等价于在图中增加一条a到b的边，由于意见具有传递性，那么他可以给在图中能到达的任何一个一个点进行投票。如果图中存在环，那么环中的每一个节点都能给其余节点投票。那么我们就可以求出强联通分量并且进行缩点，最终票数的最大值肯定存在与缩点之后出度为0的点。

在求SCC时，使用Kosaraju算法。我们首先要找到该图的后序序列，可以通过bfs来实现，然后将后序序列反向得到原图的逆后序序列，然后在原图的反图中按照逆后序序列进行dfs遍历，每次由起点遍历到的点构成一个SCC。那么处在同一个SCC的同学都可以相互投票，即每个人都能得到该SCC中的节点个数-1张票。在所有SCC都形成之后，各个SCC之间还有可能存在边，这样一个SCC中的所有成员都能给另一个SCC中的成员投票。所以我们将原图进行缩点，将处在同一个SCC中的所有点缩为1个点，然后缩点之后找到出度为0的点，然后从这个点在缩点反图中进行dfs遍历，则所有能到的点都可以对该点中的所有节点进行投票。即对于属于第i个SCC的点来说，令SCC[i] 表示第i个SCC中点的个数，答案分为两部分，一部分是当前SCC中的点，ans+=SCC[i]–1(去除自己)，第二部分是其它SCC中的点SUM( SCC[j])，其中点j可到达点i。

代码：

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
int T,N,M,rankc,sscr,allp; 
vector<int> all[5010];//存储图结构
vector<int> reverses[5010];//反图
vector<int> change[5010];//缩点后的反图
vector<int> change2[5010];//缩点后的图
int vis[5010];//用于求后序序列的dfs
int vis2[5010];//用于缩点之后求一个点的可达点的dfs
int back[5010];//存放后序序列
int ssc[5010];//存放一个点所在的scc
int sscn[5010];//某个scc的元素个数
void dfs1(int s)
{vis[s]=1;//用于求后序序列的dfsfor(int i=0;i<all[s].size();i++){int temp=all[s][i];if(vis[temp]!=1) dfs1(temp);}rankc++;back[rankc]=s;	
}
void dfs2(int s)
{ssc[s]=sscr;//用于在反图中求解scc时的dfsfor(int i=0;i<reverses[s].size();i++){int temp=reverses[s][i];if(ssc[temp]==0) dfs2(temp);}
}
void dfs3(int s)
{ allp=allp+sscn[s];//在缩点之后求解一个点所以可达点的dfsvis2[s]=1;for(int i=0;i<change[s].size();i++){int temp=change[s][i];if(vis2[temp]!=1) dfs3(temp);}
}
int main()
{cin>>T;for(int j=0;j<T;j++){rankc=sscr=allp=0;for(int i=0;i<5010;i++){//初始化vis[i]=back[i]=vis2[i]=ssc[i]=sscn[i]=0;all[i].clear();reverses[i].clear();change[i].clear();change2[i].clear(); } cin>>N>>M;for(int i=0;i<M;i++){int a,b;scanf("%d%d",&a,&b); all[a].push_back(b);//构造图和反图reverses[b].push_back(a);}for(int i=0;i<N;i++)if(vis[i]!=1) dfs1(i);//求后序序列for(int i=N;i>=1;i--){int tt=back[i];if(ssc[tt]==0)//求每一个点所在的scc{sscr++;dfs2(tt);}}for(int i=0;i<N;i++){int tt=ssc[i];//计算各个scc中点的个数sscn[tt]++;	}if(sscr==1){//如果scc只有一个，那么该scc中的所有点都能得到最大票cout<<"Case "<<j+1<<": ";cout<<N-1<<endl;for(int i=0;i<N;i++){cout<<i;if(i!=N-1)cout<<" ";}cout<<endl; }else{for(int i=0;i<N;i++){//进行缩点for(int k=0;k<reverses[i].size();k++){int te=reverses[i][k];if(ssc[i]==ssc[te]) continue;else{//缩点之后的反图change[ssc[i]].push_back(ssc[te]);//缩点之后的图change2[ssc[te]].push_back(ssc[i]);	} }	}vector<int> vp,loc; for(int i=1;i<=sscr;i++){for(int t=0;t<=sscr+1;t++)vis2[t]=0;if(change2[i].size()==0){//找到图中出度为0的点，对应反图中入度为0，在这些点中有可能有票数最大值allp=0;dfs3(i);//找到反图中所有可达点vp.push_back(allp-1);loc.push_back(i);}}int maxp=0;vector<int> allmax;for(int i=0;i<vp.size();i++){//找到票数最大值if(maxp<vp[i])maxp=vp[i];}for(int i=0;i<vp.size();i++){if(maxp==vp[i])//将所有等于最大值的scc放入allmax中allmax.push_back(loc[i]);}cout<<"Case "<<j+1<<": ";cout<<maxp<<endl;vector<int> fi;for(int i=0;i<N;i++){//遍历所有点，看其所属的scc是否在allmax中for(int z=0;z<allmax.size();z++){if(ssc[i]==allmax[z]){fi.push_back(i);break;}}}for(int i=0;i<fi.size();i++){//输出cout<<fi[i];if(i!=fi.size()-1)cout<<" ";}cout<<endl; }}
}