首页 > 代码库 > 重连通量的邻接矩阵和邻接表两种形式的求法

重连通量的邻接矩阵和邻接表两种形式的求法

邻接矩阵:

#include <cstdio>#include <cstring>#include <stack>using namespace std;#define min(a,b) a<b?a:b#define N 105int dfn[N],low[N],mat[N][N],visit[N],tmpdfn,n;struct Edge{    int x,y;    void print(){        printf("%d-%d\n",x,y);    }    bool cmp(Edge &m){        return (x==m.x&&y==m.y)||(x==m.y&&y==m.x);    }}edge[10005];stack<Edge> s;void dfs(int u){    Edge t,tt;    dfn[u]=low[u]=++tmpdfn,visit[u]=1;    for(int i=1;i<=n;i++){        if(mat[u][i]){            mat[i][u]=0;            t.x=u,t.y=i;            s.push(t);            if(!visit[i]){                dfs(i);                low[u]=min(low[u],low[i]);                if(low[i]>=dfn[u]){                    //这个while循环没有把最后匹配到的相同边输出,所以最后在pop一次                    while(!t.cmp(s.top())){                        tt=s.top();                        tt.print();                        s.pop();                    }                    tt=s.top();                    tt.print();                    s.pop();                }            }            else low[u]=min(low[u],dfn[i]);        }    }}void init(){    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(visit,0,sizeof(visit));    tmpdfn=0;}int main(){    int a,b,k;    scanf("%d",&k);    n=0;    for(int i=1;i<=k;i++){        scanf("%d%d",&a,&b);        mat[a][b]=1,mat[b][a]=1;        if(a>n) n=a;        if(b>n) n=b;    }    init();    for(int i=1;i<=n;i++)        if(!visit[i]) dfs(i);    return 0;}

邻接表:

#include <cstdio>#include <cstring>#include <stack>#include <iostream>using namespace std;#define N 105#define min(a,b) a<b?a:bint visit[N],dfn[N],low[N],first[N],tmpdfn,k,n;struct Edge{    int x, y;    void print(){        printf("%d-%d\n",x,y);    }    bool cmp(Edge &m){        return (m.x==x&&m.y==y)||(m.y==x&&m.x==y);    }};stack<Edge> s;struct Path{    int y,next,vis;}path[10005];void add(int x,int y){    path[k].y=y,path[k].next=first[x];    first[x]=k;    k++;}void init(){    memset(visit,0,sizeof(visit));    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(first,-1,sizeof(first));    k=0,tmpdfn=0;}void dfs(int u){    Edge t,tt;    dfn[u]=low[u]=++tmpdfn,visit[u]=1;    for(int i=first[u];i!=-1;i=path[i].next){        if(!path[i].vis){            t.x=u,t.y=path[i].y;            s.push(t);            path[i].vis=1,path[i^1].vis=1;            if(!visit[path[i].y]){                dfs(path[i].y);                low[u]=min(low[u],low[path[i].y]);                if(low[path[i].y]>=dfn[u]){                    while(!t.cmp(s.top())){                        tt=s.top();                        tt.print();                        s.pop();                    }                    tt=s.top();                    tt.print();                    s.pop();                }            }            else low[path[i].y]=min(dfn[u],low[path[i].y]);        }    }}int main(){    int a,b,m;    scanf("%d%d",&n,&m);    init();    for(int i=1;i<=m;i++){        scanf("%d%d",&a,&b);        add(a,b);        add(b,a);    }    for(int i=1;i<=n;i++)        if(!visit[i]) dfs(i);    return 0;}