本文共 1477 字，大约阅读时间需要 4 分钟。
题目链接：
思路：首先要判断图是否是边双连通，这个Tarjan算法可以判断，若low[v] > dfn[u],则说明边（u，v)是桥，从而这个图不是边双连通，然后发现在判断的时候已经访问了所有的顶点，顺便加入就可以了。
#include #include #include #include #include #include #include #include #define REP(i, a, b) for (int i = (a); i < (b); ++i)#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)using namespace std;const int MAX_N = (300000 + 100);int N, M, cnt, bcc_count;int low[MAX_N], dfn[MAX_N], vis[MAX_N], mark[MAX_N];stack S;vector g[MAX_N];map , int> mp;vector > edge;bool Tarjan(int u, int fa){ int tag = 0; low[u] = dfn[u] = ++cnt; vis[u] = 1; S.push(u); REP(i, 0, (int)g[u].size()) { int v = g[u][i]; if (v == fa && !tag) { tag = 1; continue; } if (!dfn[v]) { if (!Tarjan(v, u)) return false; low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) return false; else { pair PPI = make_pair(u, v); edge.push_back(PPI); mark[mp[PPI]] = 1; } } else if (vis[v]) { low[u] = min(low[u], dfn[v]); pair PPI = make_pair(u, v); if (!mark[mp[PPI]]) { mark[mp[PPI]] = 1; edge.push_back(PPI); } } } return true;}int main(){ cin >> N >> M; FOR(i, 1, M) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); mp[make_pair(u, v)] = i; mp[make_pair(v, u)] = i; } cnt = bcc_count = 0; memset(vis, 0, sizeof(vis)); memset(mark, 0, sizeof(mark)); memset(dfn, 0, sizeof(dfn)); if (!Tarjan(1, -1)) { puts("0"); return 0; } REP(i, 0, (int)edge.size()) { printf("%d %d\n", edge[i].first, edge[i].second); } return 0;}
转载地址：http://myhql.baihongyu.com/