Week 8 竞选班长

竞选班长"/>

Week 8 竞选班长

文章目录

• • 题目描述
  • 样例
  • 思路
  • 代码

题目描述

大学班级选班长，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

思路

利用kosaraju求出SCC，然后进行缩点，第一遍dfs求出逆后序序列，第二遍dfs在反图中根据逆后序序列得到所有的强连通分量

对于属于第i个SCC的点来说，答案分为两部分，令SCC[i]表示第i个SCC中的点的个数

• 当前SCC中的点，ans+=SCC[i]-1(去除自己)
• 其他SCC中的点，sum(SCC[j]) ，其中j可到达i

最后答案一定出现在出度为0的SCC中
将边反向，对于每一个入度为0的点进行dfs，计算其能到达的点sum（SCC[j]），即可得到答案

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=300010;
int head1[N],inn_[N],head2[N];
int tot1,tot2,n,m;
int c[N],dfn[N],vis[N],num[N],ans[N],temp[N],dcnt,scnt;struct Edge
{int v;int next;	
}e1[N],e2[N];void add1(int x,int y)
{e1[++tot1].v=y;e1[tot1].next=head1[x];head1[x]=tot1;
}void add2(int x,int y)
{e2[++tot2].v=y;e2[tot2].next=head2[x];head2[x]=tot2;
}void dfs1(int x)
{vis[x]=1;for(int i=head1[x];i;i=e1[i].next){int u=e1[i].v;if(!vis[u]){dfs1(u);}}dfn[++dcnt]=x;
}void dfs2(int x)
{c[x]=scnt;num[scnt]++;for(int i=head2[x];i;i=e2[i].next){int u=e2[i].v;if(!c[u]){dfs2(u);}}
}void dfs3(int u,int s)
{vis[u]=1;for(int i=head2[u];i;i=e2[i].next){int v=e2[i].v;if(!vis[v]){vis[v]=1;ans[s]+=num[v];dfs3(v,s); }}
}void kosaraju()
{dcnt=scnt=0;memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));for(int i=0;i<n;i++){if(!vis[i]) dfs1(i);}for(int i=n;i>=1;i--){if(!c[dfn[i]]) {++scnt;dfs2(dfn[i]);}}
}int main()
{int T;scanf("%d",&T);int index=0;while(T--){index++;memset(head1,0,sizeof(head1));memset(head2,0,sizeof(head2));memset(temp,0,sizeof(temp));tot1=0;tot2=0;//cin>>n>>m;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int A,B;scanf("%d%d",&A,&B);//cin>>A>>B;add1(A,B);add2(B,A);}kosaraju();memset(head2,0,sizeof(head2));tot2=0;memset(inn_,0,sizeof(inn_));for(int i=0;i<n;i++){for(int j=head1[i];j;j=e1[j].next){int u=e1[j].v;if(c[i]!=c[u]){add2(c[u],c[i]);inn_[c[i]]++;}}}memset(ans,0,sizeof(ans));int anss=0;for(int i=1;i<=scnt;i++){if(inn_[i]==0){memset(vis,0,sizeof(vis));dfs3(i,i);ans[i]+=num[i]-1;}if(ans[i]>anss){anss=ans[i];}} memset(vis,0,sizeof(vis));for(int i=1;i<=scnt;i++){if(ans[i]==anss){vis[i]=1;}}cout<<"Case "<<index<<": "<<anss<<endl;int index1=0;for(int i=0;i<n;i++){if(vis[c[i]]){temp[index1]=i;index1++;}}for(int i=0;i<index1;i++){if(i<index1-1){cout<<temp[i]<<" ";}else cout<<temp[i]<<endl;}}}