关于有向图强联通分量
摘自百度百科：
有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
即：
这两个点强联通
tarjan算法
算法简介：
摘自百度百科：
一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。
三个重要数组
first：dfn：
当前节点是第几个进来的（low[u]=dfn[u]=++index）
second:low:
当前节点通过他的儿子最远能到达第几个进来的点（low[u]=max(low[v],low[u]）
third:stack:
类似一个栈的作用，当特定时候一次性出栈（dfn[u]==low[u]）
算法运行过程：
1.进入函数，打上时间戳（low[u]=dfn[u]=++index,标记当前节点是第几个进来的）
2.进栈，打上进栈标记（s.push(u),instack[u]==1,标记它是否遍历过）
3.for循环找儿子v
3.（1）儿子没有被遍历过：low[u]=max(low[u],low[v]);
3.（2）儿子被遍历过，但还没有形成一个强连通分量： low[u]=max(low[u],dfn[v])
4.（1）如果这个节点最早只能到达它自己（low[u]==dfn[u]）,就形成了一个强连通分量，栈内元素即强连通分量里的点，站内点出栈，记录所属强连通分量，该强连通分量中的点数++（color[u]=cnt,num[cnt]++）。
4.（2）反之，继续运行下一个节点。
时间复杂度：O（N+M）
代码：
#include<bits/stdc++.h>
using namespace std;
int dfn[300001],low[300001],index,cnt,color[300001],num[300001],n,m,x,y;
bool instack[300001];
vector<int> a[300001];
stack<int> s;
void tarjan(int u)
{
low[u]=dfn[u]=++index;
instack[u]=1;
s.push(u);
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}else{
if(instack[v])
{
low[u]=min(low[u],dfn[v]);
}
}
}
if(dfn[u]==low[u])
{
int c;
cnt++;
do
{
c=s.top();
s.pop();
instack[c]=0;
color[c]=cnt;
num[cnt]++;
}while(u!=c);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
for(int i=1;i<=cnt;i++)
{
printf("%d ",num[i]);
}
puts("");
for(int i=1;i<=n;i++)
{
printf("%d ",color[i]);
}
return 0;
}
/*
3 3
1 2
2 3
1 3
*/