POJ 2186

Tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100000+10;
/*
  有n只牛,牛之间存在一些关系,比如a认为b很受欢迎
,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据
给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?

解:
  对于一个有向无环图来说,其中有且仅有一个点出度为零
,那么这个特殊的点,可以由其他任何点到达。那么接下来我
们直接对所给的图进行强连通分量划分,然后把每个强连通分
量看做一个点,判定出度为零的点有几个,如果有一个就输出
这个点对应的强连通分量含有的节点个数,否则为零。
*/
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int vis[maxn];

stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    ///如果点从1开始计数,这里改成-1即可
    G[u-1].push_back(v-1);
}

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);

    ///缩点,同一scc缩到同一点中
    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j){
            ///如果i到G[i][j]这条边不在强连通分量中
            ///说明是一个连接外面的点
            if(sccno[i]!=sccno[G[i][j]]){
                vis[sccno[i]]++;
            }
        }
    }

    int sum=0,ans=0,cnt=0;
    for(int i=1;i<=scc_cnt;++i){
        if(!vis[i]){
            ///如果出度是0,则是一个边界点
            sum++;
            ans=i;
        }
    }
    ///如果只有一个点的话,代表存在一个万人敬仰团体
    if(sum==1){
        for(int i=0;i<n;++i){
            if(sccno[i]==ans){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }else{
        printf("0\n");
    }
    return 0;
}
/*
3 3
1 2
2 1
2 3

1
*/

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数组的具体作用了.