首页 > 代码库 > POJ 1515 Street Directions --一道连通题的双连通和强连通两种解法
POJ 1515 Street Directions --一道连通题的双连通和强连通两种解法
题意：将一个无向图中的双向边改成单向边使图强连通，问最多能改多少条边，输出改造后的图。
分析：
1.双连通做法：
双连通图转强连通图的算法：对双连通图进行dfs，在搜索的过程中就能按照搜索的方向给所有边定向，其中桥不能改造，只能保留双向边。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>#include <queue>using namespace std;#define N 1006vector<pair<int,int> > G[N];int dfn[N],low[N];int Time,vis[N];bool isbge[2000010],used[2000010];int n,m,cnt;void Tarjan(int u,int father){ low[u] = dfn[u] = ++Time; vis[u] = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i].first; int id = G[u][i].second; if(v == father) continue; if(!vis[v]) { Tarjan(v,u); low[u] = min(low[u],low[v]); if(dfn[u] < low[v]) isbge[id] = 1; } else low[u] = min(low[u],dfn[v]); }}void dfs(int u,int fa){ vis[u] = 1; for(int i=0;i<G[u].size();i++) { int v = G[u][i].first; int id = G[u][i].second; if(!used[id]) { used[id] = 1; printf("%d %d\n",u,v); if(isbge[id]) printf("%d %d\n",v,u); if(!vis[v]) dfs(v,u); } }}int main(){ int i,j,u,v; int cs = 1; while(scanf("%d%d",&n,&m)!=EOF && (n||m)) { for(i=0;i<=n;i++) { G[i].clear(); vis[i] = 0; low[i] = dfn[i] = 0; } memset(used,0,sizeof(used)); memset(isbge,0,sizeof(isbge)); Time = 0; cnt = 0; //id for(i=0;i<m;i++) { scanf("%d%d",&u,&v); G[u].push_back(make_pair(v,cnt)); G[v].push_back(make_pair(u,cnt++)); //属于一条边 } for(i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,-1); memset(vis,0,sizeof(vis)); printf("%d\n\n",cs++); for(i=1;i<=n;i++) if(!vis[i]) dfs(1,-1); puts("#"); } return 0;}
2.强连通做法：
参见：http://blog.csdn.net/new_c_yuer/article/details/6733623
主要思想：在同一个连通分量里，保留单向边即可，否则需要保留双向边。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。