이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
using namespace std;
int ParLink[100005],P[100005],Lev[100005],Sz[100005],Low[100005],Covered[100005],Prv[100005],SzLink[100005];
pair<int,int> Edge[100005];
vector<pair<int,int> > A[100005];
int parentLink(int x)
{
int cx=x;
while(ParLink[x]!=0)
x=ParLink[x];
while(ParLink[cx]!=0)
{
int aux=ParLink[cx];
ParLink[cx]=x;
cx=aux;
}
return x;
}
void uniLink(int x, int y)
{
x=parentLink(x);
y=parentLink(y);
if(x==y)
return;
if(SzLink[x]>SzLink[y])
{
SzLink[x]+=SzLink[y];
ParLink[y]=x;
if(Lev[Low[y]]<Lev[Low[x]])
Low[x]=Low[y];
}
else
{
SzLink[y]+=SzLink[x];
ParLink[x]=y;
if(Lev[Low[x]]<Lev[Low[y]])
Low[y]=Low[x];
}
}
void dfs(int nod, int p, int lev, int px)
{
P[nod]=px;
Lev[nod]=lev;
for(auto other:A[nod])
if(other.first!=p)
{
Prv[other.first]=other.second;
dfs(other.first,nod,lev+1,px);
Low[parentLink(other.second)]=nod;
}
}
void unite(int x, int y, int nr)
{
int px=P[x];
int py=P[y];
if(Sz[px]<Sz[py])
{
swap(x,y);
swap(px,py);
}
Sz[px]+=Sz[py];
A[x].push_back({y,nr});
A[y].push_back({x,nr});
Prv[y]=nr;
Low[nr]=x;
ParLink[nr]=0;
SzLink[nr]=1;
dfs(y,x,Lev[x]+1,px);
}
void update(int x, int y)
{
int prvLinkx=0;
int prvLinky=0;
while(x!=y)
{
if(Lev[x]<Lev[y])
{
swap(x,y);
swap(prvLinkx,prvLinky);
}
Covered[Prv[x]]=1;
if(prvLinkx!=0)
uniLink(Prv[x],prvLinkx);
prvLinkx=Prv[x];
x=Low[parentLink(Prv[x])];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
Sz[i]=1;
P[i]=i;
Lev[i]=1;
}
int nr=0;
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
if(P[x]!=P[y])
{
nr++;
if(nr==n)
{
cout<<"-1\n";
return 0;
}
Edge[nr]={x,y};
unite(x,y,nr);
}
else
update(x,y);
}
for(int i=1; i<=nr; i++)
if(!Covered[i])
cout<<Edge[i].first<<" "<<Edge[i].second<<"\n";
return 0;
}
# | 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... |