强连通分量（WEEK8-C）
在有向图中，若一个子图中任意两点之间可连通，则称极大的强连通子图为强连通分量（SCC），如：
要求一个有向图的SCC，必须了解dfs序列的前序序列、后序序列、逆后序序列（后序序列的逆序）。
前序：dfs过程中第一次到达点x的次序，用d[x]表示。
后序：dfs中x点遍历完成的次序，用f[x]表示。
下面为求各序列的过程：
求解scc的算法：kosaraju算法，算法步骤：
例如：
代码：
应用题目：C - 班长竞选
大学班级选班长，N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适 勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？
本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。
对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2
Case 1: 2
0 1
Case 2: 2
0 1 2
解题思路
求出强连通分量后，进行缩图，将属于一个SCC的点用连通分量编号表示，存储在edges3[]中。
缩点后，对于第i个SCC，答案分为两部分：
当前 SCC 中的点，ans += SCC[i] – 1（去除自己）；
其它 SCC 中的点： SUM ( SCC[ j] )，其中 j 可到达 i。
又思考一下，发现最后答案一定出现在出度为 0 的 SCC中，因此我们将边反向，对每个入度为 0 的点进行 dfs，计算其能到达的点的 SUM(SCC[ j])，即可得到答案。
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//有向图
const int maxn=5050;
const int maxm=30010;
int vis[maxn],dfn[maxn],dcnt;
struct edge
{
int v,next;
}edges[maxm],edges2[maxm],edges3[maxm];//正图，反图 ,缩图
int head[maxn],tot,head2[maxn],tot2,head3[maxn],tot3,c[maxn],cnt,deg[maxn],vis2[maxn];
int maxV=0,cn[maxn],sum[maxn],res;//存储最大票数、每个连通分量有几个节点
void init()
{
for(int i=0;i<maxn;i++)
head[i]=-1,head2[i]=-1,head3[i]=-1,vis[i]=0,c[i]=-1,deg[i]=0,vis2[i]=0,cn[i]=0,sum[i]=0,dfn[i]=0;
tot=0,tot2=0,tot3=0,cnt=0,res=0,dcnt=0;
}
void addEdge(int _u,int _v,int type)
{
if(type==1)//原图
{
edges[tot].v=_v;
edges[tot].next=head[_u];
head[_u]=tot;
tot++;
}
else if(type==2)//反图
{
edges2[tot2].v=_v;
edges2[tot2].next=head2[_u];
head2[_u]=tot2;
tot2++;
}
else if(type==3)//缩图的反图
{
edges3[tot3].v=_v;
edges3[tot3].next=head3[_u];
head3[_u]=tot3;
tot3++;
}
}
void dfs1(int s)
{
vis[s]=1;
for(int j=head[s];j!=-1;j=edges[j].next)
{
int v=edges[j].v;
if(!vis[v])
dfs1(v);
}
dfn[++dcnt]=s;//计算逆后序序列
}
void dfs2(int s)
{
c[s]=cnt;
cn[cnt]++;//第cnt个连通分量的个数++
for(int i=head2[s];i!=-1;i=edges2[i].next)
if(c[edges2[i].v]==-1)
dfs2(edges2[i].v);
}
void dfs3(int s)
{
vis2[s]=1;
for(int i=head3[s];i!=-1;i=edges3[i].next)
if(!vis2[edges3[i].v])
{
maxV+=cn[edges3[i].v];
dfs3(edges3[i].v);
}
}
void kosarajo(int n)
{
for(int i=0;i<n;i++)
{
if(!vis[i])
dfs1(i);
}
for(int i=n;i>=1;i--)//按照逆后序顺序遍历，记录每个点属于哪个强连通分量
if(c[dfn[i]]==-1)
{
++cnt;
dfs2(dfn[i]);
}
}
void degEzero()
{
for(int i=1;i<=cnt;i++)
{
if(deg[i]==0)
{
for(int i=0;i<maxn;i++)vis2[i]=0;
maxV=cn[i]-1;
dfs3(i);
sum[i]=maxV;//存储该连通分量可到达的点的个数
if(res<maxV)res=maxV;
}
}
}
int main()
{
int t,tt=1;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
init();
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
addEdge(a,b,1);
addEdge(b,a,2);//反图
}
//找到强连通分量
kosarajo(n);
//for(int i=0;i<n;i++)printf("s%d\n",c[i]);
//建立缩图的反图
for(int i=0;i<n;i++)
for(int j=head[i];j!=-1;j=edges[j].next)
{
int v=edges[j].v;
if(c[i]!=c[v])
{
addEdge(c[v],c[i],3);//若i v属于不同的连通分量，就建立c[v]->c[i]
deg[c[i]]++;//入度增加
}
}
//找到入度为0的连通分量并计算可到达的点的个数
degEzero();
printf("Case %d: %d\n",tt,res);
int k=0;
for(int i=0;i<n;i++)
{
if(sum[c[i]]==res)
{
if(k==0){printf("%d",i);k=1;}
else printf(" %d",i);
}
}
tt++;
printf("\n");
}
return 0;
}