强连通分量(Tarjan)

//P2002解题思路:
//先求SCC,缩点后,转换为DAG(有向无环图)
//在DAG上统计入度为0的scc数量即可

//Tarjan时间复杂度:O(N+E),每个点和每条边刚好被访问一次,在空间和时间上比Kosaraju好一些。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500010;
struct edge{ int t; edge *nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[maxn];                                                         //h2是反图 
void add(int u, int v){ h[u]=new edge(v, h[u]); }
int n, m, v[maxn], st[maxn], st_k, dfn[maxn], low[maxn], timestamp, sccno[maxn], scc_cnt, scc_indegree[maxn];

void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    st[++st_k]=x, v[x]=1;                                               //v数组记录x是否在堆栈中 
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(!dfn[p->t])  tarjan(p->t), low[x]=min(low[x], low[p->t]);    //通过dfn值判断点是否访问过 
        else            if(v[p->t])   low[x]=min(low[x], low[p->t]);    //通过v值判断该点是否在堆栈中 
    }
    if(dfn[x]==low[x])                                                  //发现SCC 
    {
        sccno[x]=++scc_cnt;                                             //scc计数,同时标记x 
        while(st[st_k]!=x)
        {
            sccno[st[st_k]]=scc_cnt;
            v[st[st_k]]=0;
            st_k--;
        }
        v[st[st_k--]]=0;                                                //取消x在堆栈中的标记 
    } 
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1, b, e; i<=m; i++)
    {
        scanf("%d%d", &b, &e);
        if(b!=e)    add(b, e);                                          //去除自环 
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
    for(int i=1; i<=n; i++)                                             //统计每个scc的入度 
        for(edge *p=h[i]; p; p=p->nxt)
            if(sccno[i]!=sccno[p->t])   scc_indegree[sccno[p->t]]++;    //起点和终点不在一个scc中才统计入度 
    int ans=0; 
    for(int i=1; i<=scc_cnt; i++)       if(!scc_indegree[i]) ans++;     //统计入度为0的scc的个数 
    printf("%d\n", ans);
    return 0;
}
上一篇:0x66 Tarjan算法与无向图连通性(1)


下一篇:【ZOJ 4097-Rescue the Princess】无向图tarjan缩点+LCA