QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #798542 | #3846. Link-Cut Tree | Tom22l | TL | 0ms | 5928kb | C++17 | 1.9kb | 2024-12-04 14:41:13 | 2024-12-04 14:41:14 |
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;
}
int vis[100005];
int res=0;
int dfs(int x,int f){
vis[x]=res;
// cout<<x<<' '<<f<<' '<<res<<":"<<endl;
for(int i=h[x];i;i=nxt[i]){
if(to[i]==f) continue;
int p=to[i];
// cout<<p<<' '<<vis[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++){
flag[i]=0;
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);
}
}
bool flg=0;
for(int i=1;i<=m;i++)
if(flag[i]){
if(!flg){
flg=1;
printf("%lld",i);
}
else printf(" %lld",i);
}
printf("\n");
for(int i=1;i<=cnt;i++){
nxt[i]=0;
to[i]=0;
}
}
return 0;
}
/*
14 9
13 12
10 8
2 10
6 13
2 14
13 1
14 10
9 6
2 13
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5928kb
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:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
1658 9 20 6 4 5 8 1 7 2 3 3 8 3 1 4 8 5 3 7 6 1 6 4 9 4 1 9 3 2 5 4 5 8 9 1 8 4 2 5 7 3 6 14 78 13 12 10 8 2 10 6 13 2 14 13 1 14 10 9 6 2 13 8 3 9 8 5 6 14 12 8 1 9 14 9 5 12 6 5 10 3 12 10 4 8 5 9 10 6 8 1 6 12 4 3 13 1 5 10 3 13 9 10 13 2 5 4 7 7 1 7 6 9 3 2 12 1 10 9 1 1 14 3 1 3 4 11 1 11 6 7 1...
output:
2 5 8 3 5 7 1 3 4 2 3 4 2 3 4 7 13 1 3 4 5 9 3 4 7 12 1 2 3 8 10 11 2 3 5 7 12 13 14 15 16 1 2 3 5 1 2 4 1 3 4 1 2 3 1 2 3 10 11 15 1 5 6 1 5 7 1 2 3 4 -1 1 3 6 -1 1 2 3 5 -1 -1 6 8 9 10 11 16 1 2 6 2 3 4 -1 -1 7 8 12 13 18 -1 1 4 8 12 3 5 10 4 6 8 1 2 3 4 3 5 6 5 8 10 15 4 6 8 -1 1 2 3 5 6 1 3 4 1 ...