QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210733#3846. Link-Cut Treebeckham_of_laiwuTL 1ms5960kbC++141.4kb2023-10-11 19:32:412023-10-11 19:32:42

Judging History

你现在查看的是最新测评结果

  • [2023-10-11 19:32:42]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5960kb
  • [2023-10-11 19:32:41]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

struct qwq{
	int nxt,to,val;
};
qwq edge[N * 2];

int n,m,T,num,x,y,cnt;
int fa[N],head[N],p[N],vis[N];

void addedge(int f,int t,int v)
{
	edge[++ cnt].nxt = head[f];
	edge[cnt].to = t;
	edge[cnt].val = v;
	head[f] = cnt;
}

int getfa(int x)
{
	if(fa[x] != x) fa[x] = getfa(fa[x]);
	return fa[x];
}

int dfs(int now,int f,int tar)
{
	//printf("now = %d\n",now);
	//if(vis[now]) return 0;
	//vis[now] = 1;
	if(now == tar)
	{
		return 1;
	}
	for(int i = head[now];i;i = edge[i].nxt)
	{
		int t = edge[i].to;
		if(t == f) continue;// || vis[t]) continue;
		if(dfs(t,now,tar))
		{
			p[++ num] = edge[i].val;
			return 1;
		}
	}
}

int main()
{
	int T; 
	scanf("%d",&T);
	while(T --)
	{
		scanf("%d%d",&n,&m);
		int flag = 0;
		num = 0; cnt = 0;
		for(int i = 1;i <= n;i ++)
			fa[i] = i;
		memset(head,0,sizeof(int) * n);
		for(int i = 1;i <= m;i ++)
		{
			scanf("%d%d",&x,&y);
			if(flag) continue;
			if(getfa(x) == getfa(y))
			{
				p[++ num] = i;
				dfs(x,0,y);
				flag = 1;
			}
			else
			{
				addedge(x,y,i);
				addedge(y,x,i);
				fa[getfa(x)] = getfa(y);
			}
		}
		if(num)
		{
			sort(p + 1,p + num + 1);
			for(int i = 1;i < num;i ++)
				printf("%d ",p[i]);
			printf("%d\n",p[num]);
		}
		else printf("-1\n");
	}
	return (0 ^ 0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5960kb

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:


result: