题目链接: A Bug’s Life
题意
输入A B 代表A 喜欢 B，现在问你输入的数据里是否会出现同性恋。
思路
种类并查集，依旧是用带权的思想，类似食物链中的偏移量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <bits/stdc++.h>
using namespace std;
int val[10001],f[10001];
int Find(int x)
{
if(x != f[x])
{
int t = f[x];
f[x] = Find(f[x]);
val[x] = (val[x] + val[t]) % 2;
}
return f[x];
}
int main()
{
int N, M, t, a, b, caser = 1;
cin >> t;
while(t--)
{
printf("Scenario #%d:\n",caser++);
cin >> N >> M;
for(int i = 1; i <= N; ++i)
{
f[i] = i;
val[i] = 0;
}
int flag = 0;
for(int i = 1; i <= M; ++i)
{
cin >> a >> b;
int fa = Find(a);
int fb = Find(b);
if(fa != fb)
{
f[fa] = fb;
val[fa] = (1 + val[b] - val[a]) % 2;
}
else
{
if(val[a] == val[b])
flag = 1;
}
}
if(flag)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
cout << '\n';
}
}
|