# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
96888 | Retro3014 | Pipes (CEOI15_pipes) | C++17 | 1508 ms | 12624 KiB |
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 <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define MAX_N 100000
using namespace std;
int N, M;
vector<int> gp[MAX_N+1];
int g1[MAX_N+1], g2[MAX_N+1];
int up[MAX_N+1], lv[MAX_N+1], p[MAX_N+1];
void init(){
for(int i=1; i<=N; i++) g1[i] = g2[i] = i;
}
int find_g1(int x){
if(x==g1[x]) return x;
return g1[x] = find_g1(g1[x]);
}
int find_g2(int x){
if(x==g2[x]) return x;
return g2[x] = find_g2(g2[x]);
}
void union_g1(int x, int y){
x = find_g1(x); y = find_g1(y);
g1[x] = y;
}
void union_g2(int x, int y){
x = find_g2(x); y = find_g2(y);
g2[x] = y;
}
bool vst[MAX_N+1];
void dfs(int x){
bool tf = true;
up[x] = lv[x];
vst[x] = true;
for(int i=0; i<gp[x].size(); i++){
if(gp[x][i]==p[x] && tf){
tf = false; continue;
}
if(vst[gp[x][i]]){
up[x] = min(up[x], lv[gp[x][i]]);
}else{
p[gp[x][i]] = x;
lv[gp[x][i]] = lv[x]+1;
dfs(gp[x][i]);
if(up[gp[x][i]]>lv[x]){
printf("%d %d\n", gp[x][i], x);
}
up[x] = min(up[x], up[gp[x][i]]);
}
}
}
int main(){
scanf("%d %d", &N, &M);
init();
int a, b;
while(M--){
scanf("%d%d", &a, &b);
if(find_g1(a)!=find_g1(b)){
union_g1(a, b);
gp[a].push_back(b);
gp[b].push_back(a);
}
else if(find_g2(a)!=find_g2(b)){
union_g2(a, b);
gp[a].push_back(b);
gp[b].push_back(a);
}
}
for(int i=1; i<=N; i++){
if(!vst[i]){
lv[i] = 1;
dfs(i);
}
}
return 0;
}
Compilation message (stderr)
# | 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... |