无向图的双连通分量

说明

学习资料:

学习笔记

图的点-双连通定义:如果任意两点至少存在两条“点不重复”的路径,则说这个图是点-双连通的。

这个要求等价于任意两条边都在同一个简单环中,即内部无割点。也就是说,不含割点的图即为点-双连通图

图的边-双连通定义:如果任意两点之间至少存在两条“边不重复”的路径。

这个要求等价于每条边都至少在一个简单环中,即所有边都不是桥。也就是说,不含桥的图即为边-双连通图

特殊地,孤立点所形成的图是点-双连通的,也是边-双连通的,因为内部无割点、无割桥。

特殊地,孤立边是点-双连通的,而不是边-双连通的。

割桥将每一个边-双连通分量分开,low[i]的意义就是low[i]所连的块能返回的最早的祖先,也就是说,low[i]相同的点即为一个边连通分量。

使用方法

  • work()函数

Tips

  • 点的下标是从0~n-1
  • 使用该算法需要保证无重边
  • 跑完模版之后,所有low[i]值相同的点的集合分别为一个边-双连通分量

模版

//点-双连通分量
const int maxn=5000+10;//点数
struct Edge{
    int u,v;
    Edge(int _u,int _v){
        u = _u, v = _v;
    }
};
int pre[maxn]; //第一次访问的dfs_clock时间戳
int low[maxn];
int iscut[maxn]; //割点判断
int bccno[maxn]; // bccno[i]表示i所在最早访问的点-双联通分量的下标 即bcc[bccno[i]]这个连通分量集合中含有i这个点 对于割顶来讲没有意义,因为他属于多个点-双联通分量
vector<int> belong[maxn];//belong[i]表示i所在的双连通分量的下标的集合
int dfs_clock;
int bcc_cnt; // 双连通分量个数
vector<int>G[maxn]; // 顶点,下标0~n-1
vector<int>bcc[maxn]; //点双连通分量存储结果 下标1~bcnt
stack<Edge>S;
int dfs(int u,int fa){
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for (int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        Edge e = Edge(u, v);
        if (!pre[v]) {
            S.push(e);
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= pre[u]) {
                iscut[u] = true;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                while (true) {
                    Edge x = S.top();
                    S.pop();
                    if (bccno[x.u]!=bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                        belong[x.u].push_back(bcc_cnt);
                    }
                    if (bccno[x.v] != bcc_cnt) {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                        belong[x.v].push_back(bcc_cnt);
                    }
                    if (x.u == u && x.v ==v) {
                        break;
                    }
                }
            }

        }
        else if(pre[v] < pre[u] && v != fa){
            S.push(e);
            lowu = min(lowu, pre[v]);
        }
    }
    if (fa < 0 && child == 1) {
        iscut[u] = 0;
    }
    return  low[u]=lowu;
}
int find_bcc(int n){//n个顶点
    //栈无需清空,每次跑完必然为空
    //bcc[]无需清空,组建连通分量时已清空
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    memset(low, 0, sizeof(low));
    dfs_clock = bcc_cnt = 0;
    int cnt = 0;
    for (int i=1; i<=n; i++) {
        if (!pre[i]) {
            dfs(i, -1);
            cnt++;
        }
    }
    return cnt;
}

void work(int n,int m){// n个点 m条边
    // input and initialize
    for (int i=1; i<=n; i++) {
        G[i].clear();
        belong[i].clear();
    }
    for (int i=0; i<m; i++) {
        int u,v;
        scanf("%d%d",&u,&v);//index range: 1~n
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // find biconnected component
    int cnt = find_bcc(n);

    // output
    printf("共计%d个连通块\n",cnt);
    printf("共计%d个点-双连通分量\n",bcc_cnt);
    for (int i=1; i<=bcc_cnt; i++) {
        printf("第%d个点-双连通分量所含的点有: ",i);
        for (int j = 0; j<bcc[i].size(); j++) {
            printf("%d ",bcc[i][j]);
        }
        printf("\n");
    }
}
int main(){
    int n,m; //n个点 m条边
    while (scanf("%d%d",&n,&m)!=EOF) {
        work(n, m);
    }
}

results matching ""

    No results matching ""