# Tarjan算法求强连通分量总结

Tarjan算法求强连通分量总结

Tarjan算法原理：

1. 建立low数组（用于记录该点所在的连通子图的根节点的搜索子树所遍历的时间）与dfn数组（记录当前点遍历的时间）Index：记录搜索过程所进行的时间
2. 初始化dfn、index，当前点u的初始值为时间
3. u入栈并标记
4. 遍历与u相连的所有点（记为v）
1. 如果v未被遍历，递归遍历v点，然后更新low[u]     low[u]=min(low[u],low[v]);
2. 如果 v已经被遍历且在栈中直接更新low[u]

low[u]=min(low[u],dfn[v]);

1. 判断low[u]==low[v]如果成立，将包括u在内的所有点出栈并记录，则求得强连通分量之一
2. 继续遍历，直至结束
3. 注意：在一个图中，起点不唯一，所以tarjan算法应该遍历所有未被遍历的点(vis[i]==0)

Question:如果是有向有权图使用缩点时应该怎么处理权值的问题？

FZOJ1638求强连通分量

6 8

1 3

3 5

5 6

1 2

4 1

2 4

4 6

3 4

1 2 3 4

#include
#include
#include
using namespace std;
int first,nxt,go,arcnum=1;
int dfn,low,stack,top,dex,vis;
int rt,ans,temp,sum;
nxt[arcnum]=first[a];
first[a]=arcnum;
go[arcnum++]=b;
}
void tarjan(int u){
dfn[u]=low[u]=++dex;
stack[++top]=u; vis[u]=1;
for(int p=first[u];p!=0;p=nxt[p]){
int v=go[p];
if(vis[v]==0){
vis[v]=1;
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]==1)
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
int v; sum=0;
do{
v=stack[top--];
vis[v]=2;
temp[++sum]=v;
}while(u!=v);
if(rtfor(int i=1;i<=sum;i++)
ans[i]=temp[i];
}
}
}

int main()
{
//   freopen("in.txt","r",stdin);
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
}

for(int i=0;i<=n-1;i++)
if(vis[i]==0){
top=0;dex=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
stack[++top]=i;
tarjan(i);
}

sort(ans+1,ans+1+rt);
for(int i=1;i<=rt;i++)
printf("%d ",ans[i]);

return 0;
} Poj2186Popular Cows

Description

Every cow's dream is to become the mostpopular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you aregiven up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) thattell you that cow A thinks that cow B is popular. Since popularity is transitive,if A thinks B is popular and B thinks C is popular, then A will also think thatC is

popular, even if this is not explicitlyspecified by an ordered pair in the input. Your task is to compute the numberof cows that are considered popular by every other cow.

Input

• Line 1: Two space-separated integers, Nand M

• Lines 2..1+M: Two space-separated numbersA and B, meaning that A thinks B is popular.

Output

output

• Line 1: A single integer that is thenumber of cows who are considered popular by every other cow.

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

Hint

Cow 3 is the only cow of high popularity.

N头奶牛(N≤10000)

M对关系（a , b），表示a认为b是受欢迎的

#include
#include
#include
using namespace std;
const int MAXN=10000+200,MAXM=50000+200;
int first[MAXN],nxt[MAXM],go[MAXM],arcnum=1;
int dfn[MAXN],low[MAXN],stack[MAXM],top;
int scc[MAXN],idx,cscc,vis[MAXN];//记录强连通分量
int cd[MAXN],cd_scc[MAXN];
nxt[arcnum]=first[a];
first[a]=arcnum;
go[arcnum++]=b;
cd[a]++;
}

void tarjan(int u){
low[u]=dfn[u]=++idx;
stack[++top]=u; vis[u]=1;
for(int p=first[u];p!=0;p=nxt[p]){
int v=go[p];
if(vis[v]==0){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]==1)
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v;
cscc++;
do{
v=stack[top--];
vis[v]=2;
scc[v]=cscc;
}while(u!=v);
}
}

int main()
{
//   freopen("in.txt","r",stdin);
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
}
for(int i=1;i<=n;i++)
if(vis[i]==0)
tarjan(i);

if(idxprintf("0");
return 0;
}
for(int u=1;u<=n;u++)
for(int p=first[u];p!=0;p=nxt[p]){
int v=go[p];
if(scc[u]!=scc[v])
cd_scc[scc[u]]++;
}
int c1=0;
for(int i=1;i<=cscc;i++){
if(cd_scc[i]==0&&c1==0)
c1=i;
else if(c1!=0&&cd_scc[i]==0){
printf("0");
return 0;
}
}

int ans=0;
for(int i=1;i<=n;i++)
if(scc[i]==c1)
ans++;
printf("%d",ans);

return 0;
} 