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>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,M,vel[maxn],rod[maxn],dub[maxn],lift[maxn][17],kol[maxn];
vector<int> stablo[maxn];
void dfs(int gde,int pret){
//cout<<gde<<" "<<pret<<endl;
dub[gde]=dub[pret]+1;
lift[gde][0]=pret;
for(int i=1;i<=16;i++)
lift[gde][i]=lift[lift[gde][i-1]][i-1];
for(int x:stablo[gde])
if(x!=pret)
dfs(x,gde);
}
inline int getp(int x){
if(rod[x]==x)
return x;
rod[x]=getp(rod[x]);
return rod[x];
}
inline void spoj(int a,int b){
int oa=a,ob=b;
a=getp(a);
b=getp(b);
//cout<<a<<" ab "<<b<<endl;
if(vel[a]<vel[b]){
swap(a,b);
swap(oa,ob);
}
rod[b]=a;
vel[a]+=vel[b];
stablo[oa].push_back(ob);
stablo[ob].push_back(oa);
dfs(ob,oa);
}
inline int digni(int ko,int x){
for(int i=0;i<=16;i++)
if(x&(1<<i))
ko=lift[ko][i];
return ko;
}
inline int LCA(int a,int b){
if(dub[a]>dub[b])
swap(a,b);
if(dub[b]>dub[a])
b=digni(b,dub[b]-dub[a]);
if(a==b)
return a;
for(int i=16;i>=0;i--)
if(lift[a][i]!=lift[b][i]){
a=lift[a][i];
b=lift[b][i];
}
return lift[a][0];
}
void dfs2(int gde,int pret){
for(int x:stablo[gde])
if(x!=pret){
dfs2(x,gde);
kol[gde]+=kol[x];
}
if(pret!=0 and kol[gde]==0)
cout<<gde<<" "<<pret<<"\n";
}
int main(){
//cout<<sizeof(vel)+sizeof(rod)+sizeof(dub)+sizeof(lift)+sizeof(kol)<<endl;
int a,b;
// N=100000;
// M=6000000;
cin>>N>>M;
for(int i=1;i<=N;i++){
vel[i]=1;
rod[i]=i;
}
while(M--){
cin>>a>>b;
if(getp(a)!=getp(b))
spoj(a,b);
else{
// cout<<"DODAJEM "<<a<<" "<<b<<" "<<LCA(a,b)<<endl;
kol[a]++;
kol[b]++;
kol[LCA(a,b)]-=2;
}
}
//cout<<sizeof(stablo)<<endl;
//cin>>a;
for(int i=1;i<=N;i++)
if(dub[i]==0)
dfs2(i,0);
return 0;
}
/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/
# | 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... |