#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
int n, m, x, y, sz[100002], p[100002], dp[20][100002], depth[100002];
vector<int>G[100002];
int find (int x) {
if (p[x] == x)
return x;
return p[x] = find(p[x]);
}
void dfs2 (int x, int par) {
dp[0][x] = par;
depth[x] = depth[par] + 1;
for (int i = 1; (1 << i) < n; i++)
dp[i][x] = dp[i - 1][dp[i - 1][x]];
for (auto it : G[x]) {
if (it == par)
continue;
dfs2(it, x);
}
}
int cnt;
void merge (int x, int y) {
int px = find(x);
int py = find(y);
if (px == py)
return;
if (sz[px] > sz[py]) {
swap(x, y);
swap(px, py);
}
G[x].push_back(y);
G[y].push_back(x);
p[px] = py;
sz[py] += sz[px];
dfs2(x, y);
}
int lca (int x, int y) {
if (depth[x] > depth[y])
swap(x, y);
int d = depth[y] - depth[x];
for (int i = 0; (1 << i) <= d; i++)
if (d & (1 << i))
y = dp[i][y];
if (x == y)
return x;
for (int i = 19; i >= 0; i--)
if ((1 << i) != n && dp[i][x] != dp[i][y]) {
x = dp[i][x];
y = dp[i][y];
}
return dp[0][x];
}
int add[100002], viz[100002];
void dfs (int x, int par) {
viz[x] = 1;
for (auto it : G[x]) {
if (it == par)
continue;
dfs(it, x);
add[x] += add[it];
}
if (add[x] == 0 && par != 0)
cout << x << " " << par << "\n";
}
void dfs3 (int x, int par) {
depth[x] = depth[par] + 1;
viz[x] = 1;
sz[x] = 1e9;
for (auto it : G[x]) {
if (!viz[it]) {
dfs3(it, x);
sz[x] = min(sz[it], sz[x]);
}
else if (depth[it] < depth[x]-1) {
sz[x] = min(depth[it], sz[x]);
}
}
if (sz[x] >= depth[x] && par != 0) {
cout << x << " " << par << "\n";
}
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = i;
sz[i] = 1;
}
if (m <= 200) {
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int x = 1; x <=n; x++) {
for (int j = 0; j < G[x].size(); j++) {
int val = G[x][j];
for (int k = 1; k <= n; k++)
viz[k] = 0;
dfs3(x, {x, j});
if (!viz[val] && x < val) {
cout << x << " " << val << "\n";
}
}
}
return 0;
}
for (int i = 1; i <= m; i++) {
cin >> x >> y;
if (find(x) == find(y)) {
int L = lca(x, y);
assert(L > 0);
add[L] -= 2;
add[x]++;
add[y]++;
}
else {
merge(x, y);
//assert(abs(depth[x] - depth[y]) == 1);
}
}
for (int i = 1; i <= n; i++)
if (!viz[find(i)])
dfs(find(i), 0);
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:112:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int j = 0; j < G[x].size(); j++) {
| ~~^~~~~~~~~~~~~
pipes.cpp:116:23: error: cannot convert '<brace-enclosed initializer list>' to 'int'
116 | dfs3(x, {x, j});
| ^
| |
| <brace-enclosed initializer list>
pipes.cpp:77:23: note: initializing argument 2 of 'void dfs3(int, int)'
77 | void dfs3 (int x, int par) {
| ~~~~^~~
