重连通分量的求解

超、凢脫俗 2022-09-25 11:20 120阅读 0赞

# 重连通分量的求解 #

重连通分量：连通分量是非连通图中的极大连通子图，重连通是木有关节点的连通分量图。

![20160821083824317][]

输入顶点数和边数，边的两个顶点；输出各连通分量的每条边，每个连通分量占一行。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    using namespace std;
    #define INF 0xfffffff
    #define maxn 1010
    #define MAXN 20//顶点数最大值
    #define MAXM 40//边数最大值
    using namespace std;
    
    struct edge
    {
        int u,v;//边的两个端点
        void output()
        {
            cout<<u<<"->"<<v;
        }
        int comp(edge t)
        {
            return (u==t.u&&v==t.v)||
                   (u==t.v&&v==t.u);
        }
    } edges[MAXM];
    int se;//栈顶
    int Edge[MAXN][MAXN];//邻接矩阵（1表示有连接，2表示连接且已经走过，0表示无连接）
    int vis[MAXN];//顶点访问状态
    int n,m;//顶点数和边数
    int tmpdfn;//DFS过程中记录当前的深度优先搜索序数
    int dfn[MAXN];
    int low[MAXN];
    void dfs(int u)
    {
        for(int v=1; v<=n; v++)
        {
            if(Edge[v][u]==1)
            {
                edge t;
                t.u=u,t.v=v;
                edges[++se]=t;
                Edge[v][u]=Edge[u][v]=2;
                if(!vis[v])
                {
                    vis[v]=1;
                    tmpdfn++;
                    dfn[v]=low[v]=tmpdfn;
                    dfs(v);
                    low[u]=min(low[u],low[v]);//回退时记录顶点u的low值
                    if(low[v]>=dfn[u])//删除顶点u，子女节点v所在的子树将脱离
                    {
                        bool firstedge=true;//控制最后一条边后面木有空格的状态变量
                        while(1)
                        {
                            if(se<0) break;
                            if(firstedge) firstedge=false;
                            else cout<<" ";
                            edge t1;
                            t1=edges[se];
                            t1.output();//输出栈顶结点t1
                            edges[se].u=0;//删除栈顶t1
                            edges[se].v=0;
                            se--;
                            if(t1.comp(t)) break;
                        }
                        puts("");
                    }
                }
                else low[u]=min(low[u],dfn[v]);
            }
        }
    }
    int main()
    {
        int u,v;
        int number=1;
        while(1)
        {
            cin>>n>>m;
            if(n==0&&m==0) break;//整个输入结束
            memset(Edge,0,sizeof Edge);
            for(int i=1; i<=m; i++)
            {
                cin>>u>>v;
                Edge[u][v]=Edge[v][u]=1;
            }
            if(number>1) puts("");//保证最后一个网络的输出之后木有空行
            number++;
            low[1]=dfn[1]=1;
            tmpdfn=1;
            memset(vis,0,sizeof vis);
            vis[1]=1;
            se=-1;
            dfs(1);
        }
        return 0;
    }
    /**
    7 9
    1 2
    1 3
    1 6
    1 7
    2 3
    2 4
    2 5
    4 5
    6 7
    **/

[20160821083824317]: /images/20220718/d91b6db9bf1c45f48a29274624a5af32.png