#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int par[N], par1[N], par2[N], h[N], mnh[N], edges;
bool vis[N];
vector<pair<int, int>> bridges, g[N];
int root1(int v){
return (par1[v] == -1 ? v : par1[v] = root1(par1[v]));
}
int root2(int v){
return (par2[v] == -1 ? v : par2[v] = root2(par2[v]));
}
void merge1(int u, int v){
// cout << "merge1 : " << u << " " << v << endl;
int r1 = root1(v);
int r2 = root1(u);
par1[r1] = r2;
edges++;
g[v].push_back({u, edges});
g[u].push_back({v, edges});
}
void merge2(int u, int v){
int r1 = root2(u);
int r2 = root2(v);
if (r1 == r2)
return;
par2[r1] = r2;
edges++;
g[v].push_back({u, edges});
g[u].push_back({v, edges});
}
void dfs(int v, pair<int, int> prev = {-1, -1}){
// cout << v << endl;
vis[v] = 1;
if (prev.first == -1)
h[v] = 0;
mnh[v] = h[v];
for (auto [u, id] : g[v]){
// if (v == 59 and u == 3)
// cout << "-------HERE---------- " << id << endl;
if (prev.first == u and prev.second == id)
continue;
// cout << v << " -- " << u << endl;
mnh[v] = min(mnh[v], h[u]);
if (vis[u])
continue;
// cout << "safe" << endl;
h[u] = h[v] + 1;
par[u] = v;
dfs(u, {v, id});
mnh[v] = min(mnh[v], mnh[u]);
// cout << u << " : " << mnh[u] << endl;
if (mnh[u] >= h[u])
bridges.push_back({v, u});
}
}
// 1 -- 2 -- 3 -- 59
// void print(int v){
// cout << v << " : " << mnh[v] << endl;
// vis[v] = 1;
// for (int u : g[v])
// if (!vis[u])
// print(u);
// else if (u == 3)
// cout << "edge with 3, " << v << endl;
// }
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
scanf("%d %d", &n, &m);
for (int i=1; i<=n; i++){
par1[i] = par2[i] = -1;
mnh[i] = n + 100;
h[i] = n + 100;
}
for (int i=0; i<m; i++){
int u, v;
scanf("%d %d", &u, &v);
edges++;
g[u].push_back({v, edges});
g[v].push_back({u, edges});
// if (root1(u) != root1(v))
// merge1(u, v);
// else if (root2(u) != root2(v))
// merge2(u, v);
}
// cout << " ----------- \n";
// for (int v = 1; v <= n; v++)
// for (int u : g[v])
// if (v < u)
// cout << v << " " << u << endl;
// cout << " ----------- \n";
for (int v = 1; v <= n; v++){
if (!vis[v]){
// cout << "---------------\n";
dfs(v);
}
}
for (int i=1; i<=n; i++)
vis[i] = 0;
// printf("------ \n");
// vis[3] = 1;
// print(59);
// printf("------ \n");
// int cur = 59;
// while (par[cur]){
// cout << cur << " ";
// cur = par[cur];
// }
// cout << cur << endl;
for (auto [u, v] : bridges)
printf("%d %d\n", u, v);
}
/*
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int par1[N], par2[N], h[N], mnh[N];
bool vis[N];
vector<int> g[N];
vector<pair<int, int>> bridges;
int root1(int v){
return (par1[v] == -1 ? v : par1[v] = root1(par1[v]));
}
int root2(int v){
return (par2[v] == -1 ? v : par2[v] = root2(par2[v]));
}
void merge1(int u, int v){
int r1 = root1(v);
int r2 = root1(u);
par1[r1] = r2;
g[v].push_back(u);
g[u].push_back(v);
}
void merge2(int u, int v){
int r1 = root2(u);
int r2 = root2(v);
if (r1 == r2)
return;
par2[r1] = r2;
g[v].push_back(u);
g[u].push_back(v);
}
void dfs(int v, int p = -1){
vis[v] = 1;
mnh[v] = h[v];
for (int u : g[v]){
if (vis[u]){
if (u != p)
mnh[v] = min(mnh[v], h[u]);
continue;
}
h[u] = h[v] + 1;
dfs(u, v);
mnh[v] = min(mnh[v], mnh[u]);
if (mnh[u] >= h[u])
bridges.push_back({u, v});
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
par1[i] = par2[i] = -1;
for (int i=0; i<m; i++){
int u, v;
scanf("%d%d", &u, &v);
if (root1(u) == root1(v))
merge2(u, v);
else
merge1(u, v);
}
for (int v = 1; v <= n; v++)
if (!vis[v])
dfs(v);
for (auto [u, v] : bridges)
printf("%d %d\n", u, v);
}
*/
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
26196 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
190 ms |
36604 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
351 ms |
63556 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
522 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
617 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
784 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
736 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
729 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
