题意：将一个无向图中的双向边改成单向边使图强连通，问最多能改多少条边，输出改造后的图。
分析：
1.双连通做法：
双连通图转强连通图的算法：对双连通图进行dfs，在搜索的过程中就能按照搜索的方向给所有边定向，其中桥不能改造，只能保留双向边。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <queue> using namespace std; #define N 1006 vector<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 ",u,v); if(isbge[id]) printf("%d %d ",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 ",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
主要思想：在同一个连通分量里，保留单向边即可，否则需要保留双向边。