冲刺NOIP-011 图论连通性算法

赵思铭 · 2020-11-30 15:37:23 · 个人记录

解决联通性问题问题，无非是tarjan算法，其中作为代表的是关节，桥，强联通分量三种算法。其之后引申出缩点的技巧，拓扑排序，与图形dp（有向无环图的dp），是图论算法的难点。

在tarjan算法中有两个重要的数组dfn[i]表示时间戳，low[i]表示i或i子孙指向节点的最小dfn。

请看关节的代码：

int h[N],to[M],next[M],dfn[N],low[N],b[N];
int tot;
void add(int u,int v){
    to[++cnt]=u;
    next[cnt]=h[u];
    h[u]=cnt;
}//临接矩阵存图
void dfs(int x){
    vis[x]=1;
    dfn[x]=low[x]=++tot;
    for(int i=h[x];i;i=next[i]){
        int v=to[i];
        if(!vis[v]){
            dfs(v);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]) b[x]++;
        }
        else low[x]=min(low[x],dfn[v]);
    }
}
//in main()
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            tarjan(i);b[i]--;
        }

下面是桥的算法，只是略有区别：

int h[N],to[M],next[M],dfn[N],low[N];
int tot;
void add(int u,int v){
    to[++cnt]=u;
    next[cnt]=h[u];
    h[u]=cnt;
}//临接矩阵存图
void dfs(int x,int fa){
    vis[x]=1;
    dfn[x]=low[x]=++tot;
    for(int i=h[x];i;i=next[i]){
        int v=to[i];
        if(!vis[v]){
            dfs(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>dfn[x]) cout<<x<<" "<<v<<endl;
        }
        else if(v!=fa) low[x]=min(low[x],dfn[v]);
    }
}

下面是强联通分量的算法：

stack<int> s;
int to[M],next[M],h[M],low[N],dfn[N],ins[N],vis[N];
void tarjan(int u){
    vis[u]=ins[u]=1;
    s.push(u);
    dfn[u]=low[u]=++tot;
    for(int i=h[u];i;i=next[i]){
        int v=to[i];
        if(!vis[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        do{
            v=s.top();s.pop();ins[v]=0;
            cout<<v<<" ";
        }while(u!=v);
        cout<<endl;
    }
}

你学会了吗？