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 MAXN 100005
#define pb push_back
#define mp make_pair
using namespace std;
int n,m;
int otacs[MAXN],vels[MAXN],otaco[MAXN],velo[MAXN];
int predak(int p,int *otac,int *vel){
while(p!=otac[p]){
otac[p]=otac[otac[p]];
p=otac[p];
}
return p;
}
void spoji(int a,int b,int *otac,int *vel){
a=predak(a,otac,vel);
b=predak(b,otac,vel);
if(a==b)return;
if(vel[a]<vel[b])swap(a,b);
otac[b]=a;
vel[a]+=vel[b];
}
void init(){
for(int i=0;i<MAXN;i++){
otacs[i]=otaco[i]=i;
vels[i]=velo[i]=1;
}
}
vector<int> niz[MAXN];
bool obidjen[MAXN];
int dfs(int t,int o){
obidjen[t]=true;
int vpodst=1;
for(auto x:niz[t])
if(x!=o)
vpodst+=dfs(x,t);
if(o==0)return vpodst;
//printf(" %d %d %d\n",t,velo[predak(t,otaco,velo)],vpodst);
if(velo[predak(t,otaco,velo)]==vpodst)printf("%d %d\n",min(t,o),max(t,o));
spoji(t,o,otaco,velo);
return vpodst;
}
int main()
{
init();
scanf("%d %d",&n, &m);
for(int i=1;i<=m;i++){
int t1,t2;
scanf("%d %d",&t1,&t2);
if(predak(t1,otacs,vels)!=predak(t2,otacs,vels)){
spoji(t1,t2,otacs,vels);
niz[t1].pb(t2);
niz[t2].pb(t1);
}else{
//printf(" %d %d\n",t1,t2);
spoji(t1,t2,otaco,velo);
}
}
for(int i=1;i<=n;i++){
if(!obidjen[i]){
//printf(" %d\n",i);
dfs(i,0);
}
}
/*for(auto x:grane){
int pa=predak(x.first,otaco,velo),pb=predak(x.second,otaco,velo);
//printf(" %d %d\n",pa,pb);
if(pa>pb)swap(pa,pb); ///PAZI
if(s.find(mp(pa,pb))==s.end())s.insert(mp(pa,pb));
else s2.insert(mp(pa,pb));
}
for(auto x:grane){
int pa=predak(x.first,otaco,velo),pb=predak(x.second,otaco,velo);
if(pa>pb)swap(pa,pb); ///PAZI
if(s2.find(mp(pa,pb))==s2.end() && pa!=pb)printf("%d %d\n",x.first,x.second);
}*/
return 0;
}
Compilation message (stderr)
pipes.cpp: In function 'int main()':
pipes.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n, &m);
~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&t1,&t2);
~~~~~^~~~~~~~~~~~~~~~~
# | 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... |