<题目链接>
题目大意：
有一群孩子正在玩老鹰抓小鸡，由于想当老鹰的人不少，孩子们通过投票的方式产生，但是投票有这么一条规则：投票具有传递性，A支持B，B支持C，那么C获得2票（A.B共两票），输出最多能获得的票数是多少张和获得最多票数的人是谁？(如果有多个人获得的票数都是最多的，就将他们全部输出)。
解题分析：
不难看出，同一连通分量的所有点得到的票数肯定是相同的，所以我们先将原图进行Tarjan缩点。对于缩完点后的图，我们发现，票数最多的人一定在出度为0的"点"中，因为如果票数最多的点不是出度为0的"点"，那么它所到达的那个"点"的票数一定大于当前"点"的票数，这与当前"点"票数最多相矛盾。然后考虑对入度为0的"点"的票数统计，我们可以在缩点后进行重新构图，相互连通的"点"之间建立反边，这样方便DFS统计当前"点"的票数。需要注意的是，当前连通分量中所有的点在当前连通分量中获得的票数为num[now]-1(因为要除去自己)，然后再加上以这个点为起点，能够到达所有连通分量的点数，即为这个点能够得到的票数。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define pb push_back
#define mp make_pair
const int N = 5e3+, M = 3e4+;
int n,m,tot,cnt,cnt1,scc,top,sum;
int head[N],head1[N],low[N],dfn[N],belong[N],stk[N],instk[N],num[N],outdeg[N],vis[N],ans[N];
vector<int>G[N];
struct Edge{
int to,next;
}edge[M],edge1[M];
void init(){
rep(i,,n)G[i].clear();
tot=cnt=cnt1=scc=top=;
clr(head,-);clr(head1,-);clr(low,);clr(num,);clr(ans,);
clr(dfn,);clr(stk,);clr(instk,);clr(belong,);clr(outdeg,);
}
void addedge(int u,int v){
edge[cnt].to=v,edge[cnt].next=head[u];
head[u]=cnt++;
}
void addedge1(int u,int v){ //添加缩点后的反向边
edge1[cnt1].to=v,edge1[cnt1].next=head1[u];
head1[u]=cnt1++;
}
void Tarjan(int u){
dfn[u]=low[u]=++tot;
stk[++top]=u;instk[u]=;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(instk[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
scc++;
while(true){
int v=stk[top--];
instk[v]=;
belong[v]=scc;
G[scc].pb(v);
if(v==u)break;
}
}
}
void dfs(int u){ //统计以u连通分量为起点能够到达所有的连通分量的点数之和
vis[u]=;
sum+=num[u];
for(int i=head1[u];~i;i=edge1[i].next){
int v=edge1[i].to;
if(!vis[v])dfs(v);
}
}
int main(){
int T,ncase=;scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
rep(i,,m) {
int u,v;scanf("%d%d",&u,&v);
u++,v++;
addedge(u,v);
}
rep(i,,n) if(!dfn[i]){
Tarjan(i);
}
rep(i,,n) num[belong[i]]++; //求出每个连通分量的点数
rep(u,,n) for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
int tmp1=belong[u],tmp2=belong[v];
if( tmp1!=tmp2 ){ //缩点后，进行重新构图，并且添加的是反向边，方便进行票数的统计
addedge1(tmp2,tmp1);outdeg[tmp1]++;
}
}
int mx=-;
rep(i,,scc) if(!outdeg[i]){ //统计所有出度为0的连通分量所能够得到的票数
clr(vis,);
sum=;dfs(i);
ans[i]=sum-; //获得的票数为路径上所有的点数和-1，因为自己不能获得自己的票
mx=max(mx,ans[i]);
}
printf("Case %d: %d\n",++ncase,mx);
bool first=false;
rep(i,,n) if(ans[belong[i]]==mx){ //将所有票数等于最大票数的点输出
if(!first)printf("%d",i-);
else printf(" %d",i-);
first=true;
}puts("");
}
}
2018-12-01