#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){
// cout << "merge1 : " << u << " " << v << endl;
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){
// cout << v << endl;
vis[v] = 1;
mnh[v] = h[v];
for (int u : g[v]){
// cout << v << " -- " << u << endl;
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]);
// cout << u << " : " << mnh[u] << endl;
if (mnh[u] >= h[u])
bridges.push_back({v, u});
}
}
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;
for (int i=0; i<m; i++){
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
// 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 (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);
}
*/
/*
80 171
76 13
1 71
13 34
17 31
40 26
39 18
19 26
56 21
18 74
26 33
18 32
6 20
22 50
4 5
61 54
36 15
29 15
30 51
38 10
31 66
35 70
29 50
6 7
75 47
18 46
45 73
31 10
34 20
4 25
73 24
69 6
73 17
20 6
37 30
43 71
4 67
1 2
62 20
72 44
38 59
53 46
49 70
31 38
40 33
63 21
54 40
49 77
45 17
50 64
63 56
20 69
69 20
9 44
27 6
58 51
46 60
23 9
28 42
44 65
23 9
36 29
15 71
76 55
17 73
54 68
8 1
4 18
72 44
39 18
54 40
28 14
22 71
48 20
32 11
39 18
20 62
45 59
1 43
58 2
17 52
63 77
25 39
55 27
7 63
3 4
8 50
65 37
34 20
26 61
40 19
77 21
44 51
23 51
19 26
21 56
60 25
18 46
42 14
52 24
4 11
24 59
68 47
51 58
7 35
77 49
2 3
24 66
33 54
31 73
69 20
58 16
44 2
6 62
66 24
17 73
12 19
10 73
77 63
38 52
27 41
59 38
6 55
20 6
38 59
60 39
51 44
49 7
2 9
24 73
24 17
46 39
38 45
5 6
35 49
71 50
64 8
16 2
56 7
62 20
1 64
29 22
19 47
12 19
68 54
10 17
50 43
22 71
22 1
66 24
16 37
8 64
41 48
3 59
5 47
8 71
53 60
25 4
21 56
70 49
4 32
56 28
69 55
43 22
3 59
39 32
70 14
19 68
48 62
44 37
73 66
42 14
*/
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
3164 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
102 ms |
15952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
14420 KB |
Output is correct |
| 2 |
Runtime error |
201 ms |
30248 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
300 ms |
32792 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
401 ms |
49492 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
749 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1032 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1238 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1445 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
