Tarjan算法(模板)

算法思想： 首先要明确强连通图的概念，一个有向图中，任意两个点互相可以到达；什么是强连通分量？有向图的极大连通子图叫强连通分量。

给一个有向图，我们用Tarjan算法把这个图的子图（在这个子图内，任意两个点可以相互到达，极大的子图）缩成一个点，相当于化简；

怎样去做：从一个点开始遍历它能走到的下一个点（dfn记录时间戳，low记录能回到的最早的时间戳），每遍历到一个点,判断这个点如果没有走过(dfn值为零),继续深搜，如果走过了并且在栈里面说明可以形成一个环(那就可以缩成一个点，更新当前点low的值，回到更早的时间戳)，搜完它可以到达所有的点以后回溯，更新low；直到回到 low[u]==dfn[u]（环的“根节点"）,出栈这个点上面的所有的点（包括这个点本身,他们可以缩成一个点）.继续回溯.

特别注意：

        else if(instack[v])/*走过并且形成一个环??????*/

            low[u]=min(low[u],dfn[v]);/*更新最小值low，合并集合*/

            /*不能写成low[u]=min(low[v],low[u])*/

当计算有多少个强连通分量的时候，写成那个没关系，但是如果是求割点，两个语句求出来的low值不一样，值会偏小，割点判断错误(因为判断条件是if（low[v]>=dfn[u]）)。

扩展：

计算出入度，问加多少条边可以变成一个整个连通分量：

在这里首先缩点，用一个color[ ]数组，将同一集合的点标记成某个序号（出栈的时候就是同一集合），最后遍历输入的边，用两个数组标记每一个集合的出度入度情况，得出入度和出度分别有几个集合为零，输出最大值。注意：调用tarjan函数的时候，用for循环，因为图可能不连通！还有当它本来就是一个连通分量的时候，特判一下。

例题：POJ 1236

Network of Schools

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<iostream>

#include<vector>

#include<stack>

using namespace std;

#define N 1010

vector<int>edge[N];

vector<int>belong[N];

stack<int>s;

int low[N];/*所属的强连通数组*/

int dfn[N];/*访问的顺序*/

bool instack[N];/*是否在栈内*/

int n,m,u,v,cnt,cntb;/*n个顶点，m条边*/

void Tarjan(int u)/*当前处于的节点*/

{

    ++cnt;/*计算访问到第几个点（时间戳）*/

    dfn[u]=low[u]=cnt;/*访问的顺序(时间戳)，low数组记录这个点所能回到的最早的时间戳*/

    s.push(u);

    instack[u]=true;

    for(int i=0;i<edge[u].size();i++)/*下一个要走的节点*/

    {

        int v=edge[u][i];

        if(!dfn[v])/*如果没走过*/

        {

            Tarjan(v);/*深搜*/

            low[u]=min(low[u],low[v]);/*更新最小值low，合并集合*/

        }

        else if(instack[v])/*走过并且形成一个环??????*/

            low[u]=min(low[u],dfn[v]);/*更新最小值low，合并集合*/

    }

    if(dfn[u]==low[u])/*回到环的起点，出栈*/

    {

        ++cntb;

        int node;

        do

        {

            node=s.top();

            s.pop();

            instack[node]=false;

            belong[cntb].push_back(node);/*将集合分组*/

        }while(node!=u);

    }

}

int main()

{

    memset(instack,0,sizeof(instack));

    cnt=0;cntb=0;

    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++)

    {

        scanf("%d%d",&u,&v);

        edge[u].push_back(v);

    }

    Tarjan(1);/*从一号顶点开始遍历*/

    for(int i=1;i<=n;i++)

        printf("dfn:%d low:%d\n",dfn[i],low[i]);

    for(int i=1;i<=cntb;i++)

    {

        printf("第%d组\n",i);

        for(int j=0;j<belong[i].size();j++)

            printf("%d ",belong[i][j]);

        printf("\n");

    }

    return 0;

}

/*

7 11

1 2

2 3

2 5

2 4

3 5

3 7

7 5

5 6

6 7

4 1

4 5

*/

巴特西

Tarjan算法(模板)

最新文章

热门文章