This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 2e5;
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 parent[1 + maxn];
int timer;
void dfs(const int &cur) {
timer++;
l[cur] = d[cur] = timer;
vis[cur] = true;
for(const int &nei : graph[cur]) {
if(nei == parent[cur]) {
continue;
}
if(vis[nei]) {
l[cur] = min(l[cur], d[nei]);
} else {
parent[nei] = cur;
dfs(nei);
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);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |