结论+tarjan/dfs tree
首先图中有桥肯定无解,那么考虑不存在桥的时候怎么构造一种解。
现在图是个边双,有什么算法?tarjan。从 tarjan 入手,遍历过程将图分为了树边和返祖边(无向图中不存在横叉边和前向边,可以模拟 dfs 过程理解),那么我们可以让树边由父亲连向儿子,这样根节点就能够到达所有节点;同时可以发现,所有节点都可以到达根,因为图是边双,也就是任意节点的子树内都存在一条返祖边可以跳到该节点的祖先(如果没有这样的边,那么就是割点了)。
所以跑一遍 tarjan/dfs tree,同时定向即可。
复杂度 \(O(n)\)。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <bitset>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n, m, cnt = 1, idx, tot, num;
int h[N], dfn[N], low[N];
pii ans[N];
struct node {
int to, nxt;
} e[N << 1];
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
h[u] = cnt;
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++tot;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v, i);
ans[++num] = {u, v};
low[u] = std::min(low[u], low[v]);
} else if(i != (fa ^ 1)) {
low[u] = std::min(low[u], dfn[v]);
if(dfn[v] < dfn[u]) ans[++num] = {u, v};
}
}
if(low[u] == dfn[u]) idx++;
}
int dec[N << 1];
void Solve() {
std::cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
add(u, v), add(v, u);
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i, 0);
}
if(idx != 1) {
std::cout << "0\n";
return;
}
for(int i = 1; i <= m; i++) {
std::cout << ans[i].fi << " " << ans[i].se << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}
标签:tarjan,CF118E,int,Bertown,roads,include,节点,define
From: https://www.cnblogs.com/FireRaku/p/18161253