水题笔记_ [POI2008]CLO [并查集, SB题]

我要吐槽一下 昊哥找的题怎么越来越水了…

懵逼的 题目

扯淡的 题解

显然这个题要满足条件, 就要在一棵树的基础上再加一条边

然后我们可以在并查集上打一个”这棵树还有一条边的标记”, 然后在合并并查集的时候只要有一个集合有标记就把最终的集合标记上…最后扫一遍是不是每一个节点所属的并查集都有标记即可

沙茶的 代码

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
52
53
54
/**************************************************************
Problem: 1116
User: Cansult
Language: C++
Result: Accepted
Time:564 ms
Memory:1776 kb
****************************************************************/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXM (200000 + 5)
using namespace std;
int n, m, fa[MAXN];
bool vis[MAXN];
int find(int x)
{ return (fa[x] == x ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{
if (vis[find(x)])
vis[find(y)] = true;
fa[find(x)] = find(y);
}
int main()
{
memset(vis, false, sizeof(vis));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
if (find(srx) != find(sry))
uni(srx, sry);
else
vis[find(srx)] = true;
}
bool ok = true;
for (int i = 1; i <= n; i++)
if (!vis[find(i)])
{
ok = false;
break;
}
if (ok)
puts("TAK");
else
puts("NIE");
return 0;
}

By 沙茶 Cansult