题目描述
大学班级选班长,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开始,紧跟着是最高的票数。
接下来一行输出得票最多的同学的编号,用空格隔开,不忽略行末空格!
Sample Input
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2
Sample Output
Case 1: 2
0 1
Case 2: 2
0 1 2
思路分析
1.找到图中所有的SCC(强连通分量)
第一遍dfs确定原图的逆后序序列
第二遍dfs在反图中按照逆后序序列进行遍历
后序
:x点遍历完成的次序,即回溯时间
逆后序序列
:后序序列的逆序
2.缩点,即将互相可达与单向可达分开考虑
对于当前scc中的点,ans+=scc[i]-1(去除自己)
对于其他scc中的点,是sum即scc[j],其中j可到达i
最后答案在出度为0的SCC中。
3.将边反向,对入度为0的点进行第三遍dfs,计算其能到达点的sum
注意
1.缩点时注意:将u,v加入到c[u],c[v]时保证两个点不在同一个SCC中
2.最后答案一定在出度为0的SCC中
代码
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int t,n,m,a,b,c[5005],vis[5005],dfn[5005],dcnt,scnt;
vector<int> g1[5005],g2[5005],g3[5005];
int in[5005],scc[5005],sum[5005];
void dfs1(int x)
{
vis[x]=1;
for(int i=0;i<g1[x].size();i++)
{
if(!vis[g1[x][i]])
dfs1(g1[x][i]);
}
dfn[++dcnt]=x;
}
void dfs2(int x)
{
c[x]=scnt;
for(int i=0;i<g2[x].size();i++)
{
if(!c[g2[x][i]])
dfs2(g2[x][i]);
}
}
void kosaraju()
{
dcnt=0;
scnt=0;
memset(c,0,sizeof(c));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
if(!vis[i]) dfs1(i);
}
for(int i=n-1;i>=0;i--)
{
if(!c[dfn[i]])
{
scnt++;
dfs2(dfn[i]);
}
}
}
void solve()
{
for(int i=0;i<n;i++)
scc[c[i]]++;
for(int i=0;i<=scnt;i++)
{
in[i]=0;
g3[i].clear();
}
for(int i=0;i<n;i++)
{
for(int j=0;j<g1[i].size();j++)
{
if(c[i]!=c[g1[i][j]])
{
g3[to].push_back(u);
in[u]++;
}
}
}
}
int dfs3(int x)
{
vis[x]=1;
int ans=scc[x];
for(int i=0;i<g3[x].size();i++)
{
if(!vis[g3[x][i]])
ans+=dfs3(g3[x][i]);
}
return ans;
}
void init()
{
for(int i=0;i<n;i++)
{
g1[i].clear();
g2[i].clear();
}
memset(in,0,sizeof(in));
memset(scc,0,sizeof(scc));
memset(sum,0,sizeof(sum));
}
int main()
{
scanf("%d",&t);
for(int it=1;it<=t;it++)
{
scanf("%d %d",&n,&m);
init();
while(m--)
{
scanf("%d %d",&a,&b);
g1[a].push_back(b);
g2[b].push_back(a);
}
kosaraju();
solve();
int cnt=-1;
for(int i=1;i<=scnt;i++)
{
if(in[i]==0)
{
for(int j=1;j<=scnt;j++)
vis[j]=0;
sum[i]=dfs3(i);
cnt=max(sum[i],cnt);
}
}
printf("Case %d: %d\n",it,cnt-1);
int flag=0;
for(int i=0;i<n;i++)
{
if(sum[c[i]]==cnt)
{
if(flag==0)
printf("%d",i);
else printf(" %d",i);
flag++;
}
}
printf("\n");
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)