强连通分量

tarjan

提高dfs姿势水平:http://www.gonglin91.com/dfs-graph-edge/
配套习题食用:http://blog.csdn.net/etta19/article/details/77150602
笔记:
强连通分量只适用于有向图,时间戳不局限于此
low[u]表示在u(子树)能到达的最早遍历节点的次序
当且仅当disc[u]=low[u]时u为SCC的头结点

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+11;
struct Grpah{
    int head[maxn],V;
    int to[maxn<<1],nxt[maxn<<1],tot;
    int dfn[maxn],low[maxn],dtime;
    int sccs[maxn],sccn;
    int st[maxn],sz; bool in[maxn];
    void init(){
        sccn=dtime=sz=tot=0;
        memset(head,-1,sizeof head);
        memset(in,0,sizeof in);
        memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);
    }
    void add(int u,int v){
        to[tot]=v;
        nxt[tot]=head[u];
        head[u]=tot++;
    }
    void dfs(int u){
       int v;
       dfn[u]=low[u]=++dtime;
       in[st[sz++]=u]=1;
       for(int i = head[u]; ~i; i=nxt[i]){
           v=to[i];
           if(!dfn[v]){
               dfs(v);
               low[u]=min(low[u],low[v]);
           }
           else if(in[v]){
               low[u]=min(low[u],dfn[v]);
           }
       }
       if(dfn[u]==low[u]){
           sccn++;
           do{
               v=st[--sz];in[v]=0;
               sccs[v]=sccn;
           }while(u!=v);
           //cout<<"sccn!!! "<<sccn<<endl;
       }
   }
    void scc(){
        for(int i = 1; i <= V; i++)
            if(!dfn[i]) dfs(i);
    }
}G;
int main(){
    int from,to;G.init();
    while(cin>>from>>to){
        G.add(from,to);G.add(to,from);
    }
    G.V=10;G.scc();
    for(int i = 1; i <= 10; i++){
        cout<<i<<" "<<G.dfn[i]<<" "<<G.low[i]<<"  "<<G.sccs[i]<<endl;
    }
    return 0;
}

模板测试 HDU1269 62ms AC //肯定会A啦,毕竟是从tarjan的wiki改来的板子
POJ2186
年轻人的第一次缩点!
缩点后一定是DAG,既然是DAG那入度为0的肯定被%得最多
scc里的也一定是互相%,那缩点后的邻接边节点不是入的就是出的,
定义i为from,则出度可以轻易求出来
出度为0的有且仅有一个才能被所有牛orz,两个则scc间都%不了,就是不存在的意思

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
struct Grpah{
    int head[maxn],V;
    int to[maxn<<1],nxt[maxn<<1],tot;
    int dfn[maxn],low[maxn],dtime;
    int sccs[maxn],sccn;
    int st[maxn],sz,sn[maxn]; bool in[maxn];
    void init(){
        sccn=dtime=sz=tot=0;
        memset(head,-1,sizeof head);
        memset(in,0,sizeof in);
        memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);
        memset(sn,0,sizeof sn);
    }
    void add(int u,int v){
        to[tot]=v;
        nxt[tot]=head[u];
        head[u]=tot++;
    }
    void dfs(int u){
       int v;
       dfn[u]=low[u]=++dtime;
       in[st[sz++]=u]=1;
       for(int i = head[u]; ~i; i=nxt[i]){
           v=to[i];
           if(!dfn[v]){
               dfs(v);
               low[u]=min(low[u],low[v]);
           }
           else if(in[v]){
               low[u]=min(low[u],dfn[v]);
           }
       }
       if(dfn[u]==low[u]){
           sccn++;
           do{
               v=st[--sz];in[v]=0;
               sccs[v]=sccn;
               sn[sccn]++;
           }while(u!=v);
        //    cout<<"sccn!!! "<<sccn<<endl;
       }
   }
    void scc(){
        for(int i = 1; i <= V; i++)
            if(!dfn[i]) dfs(i);
    }
}G;
int main(){
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF){
        G.init();G.V=n;
        for(int i = 1; i <= m; i++){
            scanf("%d%d",&a,&b);
            G.add(a,b);
        }
        G.scc();
        int od[maxn];memset(od,0,sizeof od);
        for(int i = 1; i <= n; i++){//from
            for(int j = G.head[i]; ~j; j=G.nxt[j]){//to
                if(G.sccs[i]!=G.sccs[G.to[j]]&&G.sccs[i]){//not scc of i Note:0
                    od[G.sccs[i]]++;
                }
            }
        }
        int cnt=0,pos;
        for(int i = 1; i <= G.sccn; i++){
            if(!od[i]){
                cnt++;pos=i;
            }
        }
        if(cnt>1) {printf("0\n");continue;}
        else printf("%d\n",G.sn[pos]);
    }
    return 0;
}

围观dalao:http://www.cnblogs.com/DragoonKiller/p/4295943.html
POJ1236

标签: 算法, 学习

添加新评论