并查集wa了两发
查看原帖
并查集wa了两发
1229738
CyansQwQ楼主2024/5/14 16:09

a→b，那么就可以将a的父节点视作b，通过并查集，最后判断有多少个根节点，只有一个根节点的时候，其他任意节点才能到根节点（这个根节点就是我们要的答案），如果根节点的数不是1，那么一棵树上的所有节点就不能到达另一棵树的根节点。但是我的代码WA了两发

// Problem: P1700 [USACO19OPEN] Milk Factory B
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1700
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//并查集
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,fa[N],res；//res维护根节点数
int find(int x)
{
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
void unionset(int a,int b)
{
	if(find(a)!=find(b))res--;//根不同，并在一起后根节点数减1
	fa[find(a)]=find(b);
}
int main()
{
	cin>>n;res=n;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1,a,b;i<=n;i++)
	{
		cin>>a>>b;
		unionset(a,b);
	}
	//判断根节点
	if(res!=1)cout<<"-1";
	else cout<<find(1);
	
}

我拿到了其中一组数据

100
78 51
85 35
58 57
52 93
64 94
23 79
93 53
79 95
65 89
28 85
60 18
56 79
41 5
34 98
51 81
46 29
1 78
43 70
19 13
36 61
10 6
7 14
83 18
32 79
6 18
70 33
24 61
3 1
80 7
90 43
9 49
57 56
55 7
89 19
27 57
26 18
13 28
25 77
62 40
41 90
22 40
35 80
54 4
39 55
30 9
59 71
15 25
87 81
81 56
75 69
94 18
71 67
50 6
47 81
99 94
91 22
69 37
49 68
4 45
12 79
17 57
100 54
96 40
66 82
86 46
68 86
92 95
76 56
44 18
88 86
33 15
95 38
84 12
42 45
63 64
37 9
29 48
11 81
8 63
53 75
98 89
20 8
18 4
73 45
72 45
61 45
21 52
77 66
82 59
16 49
97 94
14 3
67 52
31 74
2 98
38 74
74 20
48 98
40 63
答案-1

但是我发现从1~100，所有的节点的根节点都是45，理论上答案是45，为什么是-1嘞

2024/5/14 16:09