Tarjan算法求强连通分量总结

发布于 2018-12-06  810 次阅读

 

     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求强连通分量

描述

输入一个图，输出该图中的最大强连通分量。

输入

第一行：n和m（n<=10000,m<=100000,n为节点个数，m为边的条数）

接下来m行，每行两个数：a，b，表示a指向b的边（a,b为非负整数）；

输出

输出最大强连通分量的节点，按照节点编号从小到大输出，如果有多个强连通分量节点数相同，则输出节点编号字典序较小的。

样例输入

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[10020],nxt[100200],go[100200],arcnum=1;
int dfn[10020],low[10020],stack[100200],top,dex,vis[10020];
int rt,ans[10020],temp[10020],sum;
void addarc(int a,int b){
    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);
        addarc(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是受欢迎的

关系具有传递性，即若(a,b),(b,c)→(a,c)

询问有多少头奶牛是被其他所有奶牛认为是受欢迎的

这道题据说不使用强连通算法优化也能做出来，就是说tarjan算法只是进行优化。

进过分析可以发现，在有向无环图DAG图中，要想一头（群）牛被其它所有牛欢迎，必须满足只有它自己的出度为0，其它的牛所构成的圈子（环）的出度必须大于零才可以

这样就得到了解决方法，用tarjan算法算出所有的强连通分量并将它们合并成一个点，再做一次搜索，如果这个环对外的出度为0则其中所有牛对其他牛的出度都为0

如果一个DAG图有两个以上出度为0得点，那么总有一个点无法到达其它任意一个点

遍历所有环与点，如果出度为0的只有一个则输出答案，否则答案为0

#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];
void addarc(int a,int b){
    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);
        addarc(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;
}