#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#define pii pair<int,int>
using namespace std;
const int nmax = 101;
vector <int> par(nmax);
bool marked[nmax];
int p[nmax][2];
int sz[nmax][2];
pii edge[nmax];
void make_set(int v){
p[v][0] = p[v][1] = v;
sz[v][0] = sz[v][1] = v;
par[v] = v;
}
int find_set(int v, int ind){
return p[v][ind] == v ? v : p[v][ind] = find_set(p[v][ind], ind);
}
void union_sets(int a, int b, int ind){
a = find_set(a, ind);
b = find_set(b, ind);
if(a == b)
return;
p[b][ind] = a;
sz[a][ind] += sz[b][ind];
}
set <pii> bridges;
void union_trees(int a, int b){
int A = find_set(a, 0);
int B = find_set(b, 0);
int a1 = a, b1 = b;
if(A == B)
return;
bridges.insert({a, b});
if(sz[A][0] < sz[B][0])
swap(a,b), swap(A, B);
union_sets(A, B, 0);
int last = find_set(b, 1);
par[last] = find_set(a, 1);
vector <int> path;
path.pb(last);
while(last != find_set(B, 1)){
int x = par[find_set(last, 1)];
int b1 = x;
b = find_set(x, 1);
par[b] = last;
swap(last, b);
path.pb(last);
}
for(int i = path.size() - 1; i > 0; i--){
edge[path[i]] = edge[path[i - 1]];
}
edge[path[0]] = {a1, b1};
}
void compress(int a, int b){
int x = find_set(a, 0);
a = find_set(a, 1);
b = find_set(b, 1);
int lca = find_set(x, 1);
x = find_set(x, 1);
vector <int> path_a, path_b;
while(a != x || b !=x){
path_a.pb(a);
if(marked[a]){
lca = a;
break;
}
marked[a] = true;
path_b.pb(b);
a = find_set(par[a], 1);
if(marked[b]){
lca = b;
break;
}
marked[b] = true;
b = find_set(par[b], 1);
}
for(int to : path_a){
if(to == lca) break;
bridges.erase(edge[to]);
union_sets(lca, to, 1);
}
for(int to : path_b){
if(to == lca) break;
bridges.erase(edge[to]);
union_sets(lca, to, 1);
}
for(int to : path_a)
marked[to] = false;
for(int to : path_b)
marked[to] = false;
}
void add_edge(int a, int b){
if(find_set(a, 0) != find_set(b, 0)){
union_trees(a, b);
}
else{
if(find_set(a, 1) == find_set(b, 1))
return;
compress(a, b);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i++){
make_set(i);
}
int u, v;
for(int i= 1; i <= m; ++i){
cin >> u >> v;
add_edge(u, v);
}
for(auto to : bridges)
cout << to.f << ' ' << to.s << "\n";
}
Compilation message
pipes.cpp: In function 'void union_trees(int, int)':
pipes.cpp:56:13: warning: unused variable 'b1' [-Wunused-variable]
56 | int b1 = x;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
464 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
