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];
vector<pair<int,int>> R;
vector<int> V;
void dfs(int gde,int pret){
V.push_back(gde);
lift[gde][0]=pret;
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,bool ost=false){
int oa=a,ob=b;
a=getp(a);
b=getp(b);
if(vel[a]<vel[b]){
swap(a,b);
swap(oa,ob);
}
rod[b]=a;
vel[a]+=vel[b];
if(ost){
stablo[oa].push_back(ob);
stablo[ob].push_back(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];
}
int main(){
/*
ifstream inf;
ofstream ouf;
inf.open("Input.txt");
ouf.open("Output1.txt");
#define cin inf*/
// #define cout ouf
int a,b;
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,true);
}
for(int i=1;i<=N;i++)
if(lift[i][0]==0)
dfs(i,0);
dub[0]=-1;
for(int x:V)
dub[x]=dub[lift[x][0]]+1;
for(int j=1;j<=16;j++)
for(int i=1;i<=N;i++)
lift[i][j]=lift[lift[i][j-1]][j-1];
cin.clear(); // Clear the EOF flag
cin.seekg(0, std::ios::beg);
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)){
kol[a]++;
kol[b]++;
kol[LCA(a,b)]-=2;
}
else
spoj(a,b,false);
}
int x;
for(int i=V.size()-1;i>=0;i--){
x=V[i];
for(int y:stablo[x])
if(y!=lift[x][0])
kol[x]+=kol[y];
if(kol[x]==0 and lift[x][0]!=0)
R.push_back({min(x,lift[x][0]),max(x,lift[x][0])});
}
sort(R.begin(),R.end());
for(auto x:R)
cout<<x.first<<" "<<x.second<<"\n";
// inf.close();
// ouf.close();
return 0;
}
/*
10 13
2 6
7 2
5 10
10 3
3 4
5 8
9 7
4 2
7 9
5 8
1 3
3 7
2 1
*/
# | 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... |