图论-无向图连通性

Filberte · 2023-09-21 15:04:14 · 算法·理论

连通性相关问题是图论中比较重要的一部分，其具有较大的现实性意义（所以比较好拿来出题）。本文主要介绍无向图中相关问题。

基础概念

将后文所有需要用的概念都放这里了。（感性理解，要严格定义去看 oi-wiki）

联通：两点之间相互可达。

联通图：某个图中，任意两点之间都联通。

联通分量：极大的联通子图（再加任意一条边/一个点进来都不是联通子图了）。

DFS 树（森林）：采用 DFS 的方式遍历一个图，所经过的边和点构成的一棵树称之为原图的 DFS 树（森林）。原图是个联通图就是树，否则就是森林。

树边/非树边：在 DFS 树上的边就是树边，反之就是非树边。

时间戳（dfn）：按照 DFS 遍历原图，每个点被访问到的时间顺序。

追溯值（low）：不经过其父亲节点能到达的时间戳最小的点的时间戳（怎么这么拗口）。

割点（割顶）：对于一个无向图，如果把某个点以及连接这个点的边删掉后这个图的联通分量数增加了，那么这个点就是这个图的割点（割顶）。

割边（桥）：对于一个无向图，如果把某条边删掉后这个图的联通分量数增加了，那么这条边就是这个图的割边（桥）。

边双联通图：一个没有桥的联通图。

边双联通分量：极大的边双联通图。

点双联通图：一个没有割点的联通图。

点双联通分量：极大的点双联通图。

无向图的 Tarjan 算法

其实就是求解 dfn 数组和 low 数组的过程。

算法流程：DFS 遍历原图，在 DFS 的过程中维护出 dfn 的值。对于某个点 u ，遍历它相邻的点 v（v \not= fa_u）。若 v 是 u 的儿子，那么 low_u = \min(low_u,low_v)，否则 low_u = \min(low_u,dfn_v)。

大致代码如下：

void tarjan(int u , int father){
    dfn[u] = low[u] = ++clk;
    for(int v : g[u]){
        if(!dfn[v]){
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
        }
        else if(v != father) low[u] = min(low[u] , dfn[v]);
    }
} 

割点与桥、双联通分量、缩点

割点的判定：对于一个点 u ，若它存在至少一个儿子 v，使得 low_v \ge dfn_u，也就是说 v 不经过 u 回不到祖先了，那么 u 就是原图的一个割点。但是当 u 是根的时候，这个判定法则就不对了（它的儿子的追溯值永远不可能比它的时间戳小）。此时判定法则改为它是否有两个及以上的子节点，若有，则为割点，反之就不是。

题目连接：洛谷-P3388

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
int dfn[N] , low[N] , clk;
int id[N];
int n , m;
bool cut[N];
vector <int> g[N];
int ans;
void tarjan(int u , int fa){
    dfn[u] = low[u] = ++clk;
    int ch = 0;
    for(int v : g[u]){
        if(!dfn[v]){
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
            if(fa == 0 ? ++ch > 1 : low[v] >= dfn[u]) cut[u] = 1;
        }       
        else if(v != fa) low[u] = min(low[u] , dfn[v]);
    }
    if(cut[u]) ans++;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u , v;scanf("%d%d",&u,&v);
        g[u].push_back(v);g[v].push_back(u);
    }
    for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i , 0);
    printf("%d\n",ans);
    for(int i = 1;i <= n;i++) if(cut[i]) printf("%d ",i); 
    return 0;
} 

桥的判定：首先，非树边肯定不是桥，（毕竟有你没你一个样）。对于树边，跟割点类似，对于一个点 u ，若它存在至少一个儿子 v，使得 low_v > dfn_u，也就是说 v 不经过 u 回不到祖先了，那么 (u,v) 就是原图的桥。

由于不用特殊判断根节点，甚至比割点好写，嘻嘻~

题目链接：UVA-796

代码：

#include <bits/stdc++.h>
#define Pair pair<int , int>
#define pbp(x , y) push_back(make_pair(min(x,y) , max(x,y)))
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 100;
int dfn[N] , low[N] , clk;
vector <Pair> ans;
vector <int> g[N];
int cnt;
int n;
void tarjan(int u , int fa){
    dfn[u] = low[u] = ++clk;
    for(int v : g[u]){
        if(!dfn[v]){
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
            if(low[v] > dfn[u]) ans.pbp(u , v);
        }       
        else if(v != fa) low[u] = min(low[u] , dfn[v]);
    }
}
void init(){
    memset(dfn , 0 , sizeof(dfn));
    memset(low , 0 , sizeof(low));
    clk = 0;
    for(int i = 0;i < n;i++) g[i].clear();
    ans.clear();
}
int main(){
    while(scanf("%d",&n) != EOF){
        init(); 
        int u , v , k;
        for(int i = 0;i < n;i++){
            scanf("%d (%d)",&u,&k);
            while(k--){
                scanf("%d",&v);
                g[u].pb(v);
            }
        }
        for(int i = 0;i < n;i++) if(!dfn[i]) tarjan(i , -1);
        sort(ans.begin(),ans.end());
        printf("%d critical links\n",(int)ans.size());
        for(Pair x : ans) printf("%d - %d\n",x.fi,x.se);
        puts("");
    }
    return 0;
} 

边双联通分量的求法：根据定义，边双联通分量没有桥。于是将把原图中的桥去掉，新图中每个联通块都会对应一个边双联通分量了。

题目链接：洛谷-P8436

代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e5 + 100;
const int M = 4e6 + 100;
int n , m;
int dfn[N] , low[N] , clk;
int h[N] , nxt[M] , to[M] , idx = 1;
int b[M];
int dcc[N];
void add(int u , int v){
    if(u == v) return ; 
    nxt[++idx] = h[u];
    to[idx] = v;
    h[u] = idx;
    nxt[++idx] = h[v];
    to[idx] = u;
    h[v] = idx;
} 
void tarjan(int u , int in){
    dfn[u] = low[u] = ++clk;
    for(int i = h[u];i;i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v , i);
            low[u] = min(low[u] , low[v]);
            if(low[v] > dfn[u]) b[i] = b[i ^ 1] = 1;
        }       
        else if(i != (in ^ 1)) low[u] = min(low[u] , dfn[v]);
    }
}
int cnt;
vector<int> ans[M];
void dfs(int u){
    dcc[u] = cnt;
    ans[cnt].push_back(u);
    for(int i = h[u];i;i = nxt[i]){
        int v = to[i];
        if(!dcc[v] && !b[i]) dfs(v);
    } 
}

int main(){  
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u , v;
        scanf("%d%d",&u,&v); 
        add(u , v); 
    }
    for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i , 0);
    for(int i = 1;i <= n;i++) if(!dcc[i]){
        ++cnt; 
        dfs(i);
    }
    printf("%d\n",cnt);
    for(int i = 1;i <= cnt;i++){
        printf("%d ",(int)ans[i].size());
        for(int nod : ans[i]) printf("%d ",nod);
        puts("");
    }
    return 0;
}

点双联通分量的求法：在 Tarjan 算法的过程中，维护一个栈。当一个点第一次被访问时，将其入栈。当某个点 u 存在一个子节点 v，使得 dfn_u \le low_v 时，从栈顶不断弹出节点，直到 v 被弹出。然后刚才弹出的所有点和 u 共同构成一个点双联通分量。

题目链接：洛谷-P8435

代码：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e5 + 100;
int dfn[N] , low[N] , clk;
int stk[N] , tp; 
int id[N];
int n , m;
bool cut[N];
vector <int> g[N];
int rt;
vector<int> vdcc[N];
int cnt;
void tarjan(int u , int fa){
    dfn[u] = low[u] = ++clk;
    stk[++tp] = u; 
    int ch = 0;
    for(int v : g[u]){
        if(!dfn[v]){
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
            if(low[v] >= dfn[u]){
                if(u != rt || ++ch > 1) cut[u] = 1;
                vdcc[++cnt].pb(u);
                int now; 
                do{
                    now = stk[tp--];
                    vdcc[cnt].pb(now);
                }while(now != v);

            }
        }       
        else if(v != fa) low[u] = min(low[u] , dfn[v]);
    }
    if(!fa && !ch) vdcc[++cnt].pb(u);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int u , v;scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);
    }
    for(int i = 1;i <= n;i++) if(!dfn[i]){
        rt = i , tp = 0;
        tarjan(i , 0);  
    }
    printf("%d\n",cnt);
    for(int i = 1;i <= cnt;i++){
        printf("%d ",(int)vdcc[i].size());
        for(int v : vdcc[i]) printf("%d ",v);
        puts("");
    }
    return 0;
} 

例题及扩展应用

……感觉这些题出的都好模板。

洛谷-P2860

一句话题意：往图中加一些边，使得原图是个边双连通图。问最少需要加多少条边。

显然先求边双联通分量，然后缩点。题目保证原图联通，则缩点后一定是一棵树。否则如果有环，这些环上的点可以构成边双，继续缩点。

先给一个结论：假设这棵树中度数为 1 的点的数量是 cnt，那么必然可以通过多连 \left\lceil\frac{cnt}{2}\right\rceil 条边的方式，让原图变成一个边双联通图。

我们一步步来证明它：首先如果原图中所有点度数都大于 1 了，则原图肯定边双联通。对于度数为 2 的点，我们无需考虑，毕竟只要它连接的两个点都满足题意，它就肯定满足题意。现在只需证每连一条边，都会让度数为 1 的点的数量减少两个（在只剩 1 个点的时候减少一个）。

分两种情况讨论：若图中还存在两个度数为 1 的点 x,y 且 dis(x,y) \ge 3，即两点间还有至少 2 个点，那么把 x,y 连边后， x,y 和它们路径上的所有点构成的边双联通分量缩成的点度数肯定不为 1 （如图左），我们成功减少了两个度数为 1 的点。若不存在，则原图必然是一个菊花图（如图右），随便挑 2 个度数为 1 的点，把他们连边，也能较少 2 个度数为 1 的点。

综上，我们证明了只需要 \left\lceil\frac{cnt}{2}\right\rceil 步，就可以把原图变成一个双联通图。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5050 , M = 20050;
int dfn[N] , low[N] , clk , b[M];
int h[N] , nxt[M] , ver[M] , idx = 1;
int dcc[N] , cnt;
vector<int> g[N];
void add(int u , int v){
    nxt[++idx] = h[u];ver[idx] = v;h[u] = idx;
    nxt[++idx] = h[v];ver[idx] = u;h[v] = idx;
} 
void tarjan(int u , int in){
    dfn[u] = low[u] = ++clk;
    for(int i = h[u];i;i = nxt[i]){
        int v = ver[i];
        if(!dfn[v]){
            tarjan(v , i);
            low[u] = min(low[u] , low[v]);
            if(low[v] > dfn[u]) b[i] = b[i ^ 1] = 1;
        }
        else if(i != (in ^ 1)) low[u] = min(low[u] , dfn[v]);
    }
}
void dfs(int u){
    dcc[u] = cnt;
    for(int i = h[u];i;i = nxt[i]){
        int v = ver[i];
        if(!dcc[v] && !b[i]) dfs(v);
    }
}
int n , m , u , v;
int in[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        scanf("%d%d",&u,&v); 
        add(u , v); 
    }
    tarjan(1 , 0);
    for(int i = 1;i <= n;i++) if(!dcc[i]) cnt++,dfs(i);
    for(u = 1;u <= n;u++){
        for(int i = h[u];i;i = nxt[i]){
            v = ver[i];
            if(dcc[u] != dcc[v]) in[dcc[v]]++;
        }
    }
    int ans = 0;
    for(int i = 1;i <= cnt;i++) if(in[i] == 1) ans++;
    printf("%d\n",(ans + 1) / 2);
    return 0;
}

HDU-4738

好像又是模板。注意细节，本身不联通就不需要炸桥，输出 0；没有桥永远炸不掉，输出 -1；即使最小的代价是 0 也要人去炸桥，输出 1。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const int inf = 1e9;
const int M = 2e6 + 100;
int n , m , ans;
int dfn[N] , low[N] , clk;
int h[N] , nxt[M] , to[M] , idx = 1 , w[M];
void add(int u , int v , int val){
    nxt[++idx] = h[u];
    to[idx] = v;
    w[idx] = val;
    h[u] = idx;
    nxt[++idx] = h[v];
    to[idx] = u;
    w[idx] = val;
    h[v] = idx;
    return ;
} 
void tarjan(int u , int in){
    dfn[u] = low[u] = ++clk;
    for(int i = h[u];i;i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v , i);
            low[u] = min(low[u] , low[v]);
            if(low[v] > dfn[u]) ans = min(ans , w[i]);
        }       
        else if(i != (in ^ 1)) low[u] = min(low[u] , dfn[v]);
    }
}
void init(){
    for(int i = 1;i <= n;i++) dfn[i] = low[i] = 0;
    clk = 0 , idx = 1 , ans = inf;
    memset(h , 0 , sizeof(h));
}
int main(){ 
    while(scanf("%d%d",&n,&m) != EOF){
        if(!n && !m) break;
        init();
        for(int i = 1;i <= m;i++){
            int x , y , z;
            scanf("%d%d%d",&x,&y,&z);
            add(x , y , z);
        }
        int flag = 0;
        for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i , 0) , flag++;
        if(flag > 1) puts("0");
        else printf("%d\n",(ans == inf) ? -1 : ((ans == 0) ? 1 : ans));
    }
    return 0;       
}