首页 > 代码库 > 重连通量的邻接矩阵和邻接表两种形式的求法
重连通量的邻接矩阵和邻接表两种形式的求法
邻接矩阵:
#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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。