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;
mt19937 rng(time(0));
const int mxN=1e5+2;
vector<int>adj[mxN];
int ln[mxN],dp[mxN];
bitset<mxN>vv;
int finde(int&x){
return x==ln[x]?x:ln[x]=finde(ln[x]);
}
void merge(int u,int v){
ln[finde(u)]=finde(v);
}
void dfs(int&u,int&p){
vv[u]=1;
for(int&v:adj[u]){
if(!(v^p))
continue;
dfs(v,u);
dp[u]^=dp[v];
}
}
void res(int&u,int&p){
vv[u]=1;
for(int&v:adj[u]){
if(!(v^p))
continue;
res(v,u);
if(!dp[v])
cout<<u<<' '<<v<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
iota(ln,ln+n+1,0);
for(int i=0,u,v;i<m;++i){
cin>>u>>v;
if(finde(u)==finde(v)){
int xx=rng();
dp[u]^=xx;
dp[v]^=xx;
}else{
merge(u,v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
vv.reset();
for(int fi=1,u,p;fi<=n;++fi){
if(vv[fi])
continue;
u=fi,p=0;
dfs(u,p);
}
vv.reset();
for(int fi=1,u,p;fi<=n;++fi){
if(vv[fi])
continue;
u=fi,p=0;
res(u,p);
}
}
# | 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... |