#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1e5;
int n, m;
vector<int> graph[1 + maxn];
int par[1 + maxn];
int sz[1 + maxn];
int par2[1 + maxn];
int sz2[1 + maxn];
void make_set2(int a) {
par2[a] = a;
sz2[a] = 1;
}
int find_set2(int a) {
if(a == par2[a]) {
return a;
}
return par2[a] = find_set2(par2[a]);
}
/*void union_sets2(int a, int b) {
a = find_set2(a), b = find_set2(b);
if(a == b) {
return;
}
if(sz2[a] < sz2[b]) {
swap(a, b);
}
par2[b] = a;
sz2[a] += sz2[b];
}*/
void make_set(int a) {
par[a] = a;
sz[a] = 1;
}
/*int find_set(int a) {
if(a == par[a]) {
return a;
}
return par[a] = find_set(par[a]);
}
void union_sets(int a, int b) {
int ax = a, bx = b;
a = find_set(a), b = find_set(b);
if(a == b) {
union_sets2(ax, bx);
return;
}
graph[ax].pb(bx);
graph[bx].pb(ax);
if(sz[a] < sz[b]) {
swap(a, b);
}
par[b] = a;
sz[a] += sz[b];
}*/
bool vis[1 + maxn];
int l[1 + maxn];
int d[1 + maxn];
int timer;
void dfs(int cur, int parent) {
timer++;
l[cur] = d[cur] = timer;
vis[cur] = true;
for(int nei : graph[cur]) {
if(nei == parent) {
continue;
}
if(vis[nei]) {
l[cur] = min(l[cur], d[nei]);
} else {
dfs(nei, cur);
l[cur] = min(l[cur], l[nei]);
if(l[nei] > d[cur] && cur <= n && nei <= n) {
cout << cur << " " << nei << "\n";
}
}
}
}
void solve() {
cin >> n >> m;
int x, y;
for(int i = 1; i <= n; i++) {
make_set(i);
}
for(int i = 1; i <= n; i++) {
make_set2(i);
}
int a, b;
for(int i = 1; i <= m; i++) {
cin >> x >> y;
//union_sets(x, y);
a = x, b = y;
while(par[a] != a) {
a = par[a];
}
while(par[b] != b) {
b = par[b];
}
if(a == b) {
a = x, b = y;
while(par2[a] != a) {
a = par2[a];
}
while(par2[b] != b) {
b = par2[b];
}
if(a == b) {
// -
} else {
if(sz2[a] < sz2[b]) {
swap(a, b);
}
par2[b] = a;
sz2[a] += sz2[b];
}
} else {
graph[x].pb(y);
graph[y].pb(x);
if(sz[a] < sz[b]) {
swap(a, b);
}
par[b] = a;
sz[a] += sz[b];
}
}
for(int i = 1; i <= n; i++) {
int j = find_set2(i) + n;
graph[i].pb(j);
graph[j].pb(i);
}
for(int i = 1; i <= 2 * n; i++) {
if(!vis[i]) {
dfs(i, -1);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5216 KB |
Output is correct |
2 |
Correct |
3 ms |
5212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
5168 KB |
Output is correct |
2 |
Correct |
70 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
124 ms |
5360 KB |
Output is correct |
2 |
Correct |
145 ms |
5368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
223 ms |
6360 KB |
Output is correct |
2 |
Correct |
181 ms |
6664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
265 ms |
15816 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
435 ms |
16528 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
574 ms |
16124 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
732 ms |
16212 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
857 ms |
15964 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |