Tarjan 强连通分量算法

Lrj中还说了一种求强连通分量的算法: Kosaraju算法.
但Tarjan算法的常数比Kos小,所以作为常用算法,我们直接学习Tarjan算法即可.

学习契机: HDU 6038

首先介绍下:

强连通分量:

画图以明志 —

Tarjan算法的时间复杂度是线性的,而kos算法则需要计算图的转置.该算法由Tarjan于1972年提出,是SCC(Strongly Connected Componenet,强连通分量)的第一个线性算法,Tarjan算法借助于DFS,但它并不需要靠遍历顺序(Kos算法的思想)来分离SCC,而是允许SCC并存于同一颗DFS树中,然后通过某种手段将他们分开.

DAG:

如果把一个集合看成一个点,那么所有的SCC构成了一个SCC图.这个SCC图不会存在有向环,因此是一个DAG(Directed Acyclic Graph,有向无环图).
那他喵的什么是DAG呢?我把上面的那个强连通分量图给DAG化:

算法流程

考虑强连通分量C,设其中第一个被发现的点为x,则C中其他点都是x的后代.我们希望在x dfs访问完成后立即输出C.这样,就可以在一棵DFS树中区分开所有SCC了.因此,问题的关键是如何发现每个SCC的第一个点.

如何判断是否是SCC顶点


假设我们正在判断u是否为某SCC的第一个被发现节点.如果我们发现从u的子节点出发可以达到u的祖先w,显然u就不是SCC的顶点.反之,如果SCC最远的顶点可以到u,则u是SCC的顶点.图中虚线表示一条或多条边和点.
我们使用两个数组来记录每个节点的状态.pre[]和lowlink[].
当递归回溯时如果这两个数组的值相同,则表明该节点为某SCC顶点.

证明

见: http://blog.csdn.net/keyboarderqq/article/details/71308102

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;

vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    printf("SCC个数: %d\n",scc_cnt);

    for(int i=0;i<n;++i){
        printf("点 %d 的 SCC 编号是: %d\n",i,sccno[i]);
    }
    return 0;
}
/*
6 6

1 0
0 4
4 5
5 1
1 2
2 3
*/

此致:画个图你就知道low数组的具体作用了.

AOJ ALDS1_11_D Connected Components

Connected Components

Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.

Input

In the first line, two integer n and m are given. n is the number of users in the SNS and m is the number of relations in the SNS. The users in the SNS are identified by IDs 0, 1, …, n-1.

In the following m lines, the relations are given. Each relation is given by two integers s and t that represents s and t are friends (and reachable each other).

In the next line, the number of queries q is given. In the following q lines, q queries are given respectively. Each query consists of two integers s and t separated by a space character.

Output

For each query, print “yes” if t is reachable from s through the social network, “no” otherwise.

Constraints

  • 2 \leq n \leq 100,000
  • 0 \leq m \leq 100,000
  • 1 \leq q \leq 10,000

Sample Input

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

Sample Output

yes
yes
no

求连通分量,对每一个连通分量进行染色.不在同一个联通分量的肯定无法联系.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
const int maxn=100000;
const int NIL=-1;
int n;
vector<int> G[maxn];
int color[maxn];

void dfs(int r,int c){
    stack<int> S;
    S.push(r);
    color[r]=c;
    while(!S.empty()){
        int u=S.top();S.pop();
        for(int i=0;i<G[u].size();++i){
            int v=G[u][i];
            if(color[v]==NIL){
                color[v]=c;
                S.push(v);
            }
        }
    }
}

void setColor(){
    int id=1;
    for(int i=0;i<n;++i){
        color[i]=NIL;
    }
    for(int u=0;u<n;++u){
        if(color[u]==NIL) dfs(u,id++);
    }
}

int main(){
    int s,t,m,q;

    cin>>n>>m;

    for(int i=0;i<m;++i){
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    setColor();

    cin>>q;
    for(int i=0;i<q;++i){
        cin>>s>>t;
        if(color[s]==color[t]){
            puts("yes");
        }else{
            puts("no");
        }
    }

    return 0;
}