QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798522 | #3846. Link-Cut Tree | Tom22l | WA | 0ms | 3820kb | C++17 | 1.7kb | 2024-12-04 14:26:10 | 2024-12-04 14:26:11 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int fa[100005];
int findf(int x){
if(fa[x]==x) return x;
return fa[x]=findf(fa[x]);
}
int h[100005];
int to[100005];
int nxt[100005];
int cnt;
bool flag[100005];
void link(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
nxt[++cnt]=h[y];
h[y]=cnt;
to[cnt]=x;
return;
}
bool vis[100005];
int res=0;
int dfs(int x,int f){
vis[x]=res;
// cout<<x<<' '<<f<<":"<<endl;
for(int i=h[x];i;i=nxt[i]){
if(to[i]==f) continue;
int p=to[i];
// cout<<p<<endl;
if(vis[p]==res){
flag[i/2]=1;
return p;
}if(vis[p]) continue;
int k=dfs(p,x);
if(k){
flag[i/2]=1;
if(k==x)return 0;
return k;
}
}
// cout<<x<<' '<<f<<"end"<<endl;
return 0;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=Read();
while(T--){
int n=Read(),m=Read();
cnt=1;
for(int i=1;i<=n;i++) fa[i]=i,h[i]=0,vis[i]=0;
bool fl=0;
for(int i=1;i<=m;i++){
int x=Read(),y=Read();
if(fl)continue;
int fax=findf(x),fay=findf(y);
if(fax==fay)
fl=1;
fa[fax]=fay;
link(x,y);
}
res=0;
if(!fl){
printf("-1\n");
for(int i=1;i<=cnt;i++){
nxt[i]=0;
to[i]=0;
}
continue;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
res++;
dfs(i,0);
}
}
for(int i=1;i<=m;i++)
if(flag[i])
printf("%lld ",i);
printf("\n");
for(int i=1;i<=cnt;i++){
nxt[i]=0;
to[i]=0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3820kb
input:
2 6 8 1 2 2 3 5 6 3 4 2 5 5 4 5 1 4 2 4 2 1 2 4 3
output:
2 4 5 6 -1
result:
wrong answer 1st lines differ - expected: '2 4 5 6', found: '2 4 5 6 '