Overcooked!(并查集区间元素合并优化)
原创 于 2024-03-27 21:00:36 发布 · 粉丝可见 · 509 阅读 · 9 · 4 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137088845
本题链接： 登录—专业IT笔试面试备考平台_牛客网 登录—专业IT笔试面试备考平台_牛客网 登录—专业IT笔试面试备考平台_牛客网
题目：
样例：
cobol<br/>5 5<br/>1 1 2<br/>3 1 2<br/>2 2 4<br/>3 1 4<br/>3 2 5<br/> |
思路：
根据题意，这是个模板的并查集，但是多了一个操作，就是合并区间多个元素为一个集合。
其中合并区间多个元素为一个集合的核心是，存一个区间合并的 ne 数组。
初始化操作
1
2
3
4
5
|
inline Init()
{
for(int i = 1;i <= n ;++i) f[i] = i,ne[i] = i + 1;
}
|
多个元素区间合并操作
1
2
3
4
5
6
7
8
| int L = a,R = b;
int t = ne[L];
for(int i = L ;i <= R;i = t)
{
Union(i,R);
t = ne[i];
ne[i] = ne[R];
}
|
具体合并优化过程，跟着代码，在草稿纸上模拟走一遍就思路清晰了。
AC代码如下：
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
signed main()
{
IOS;
int _t = 1;
while (_t--)
{
solve();
}
return 0;
}
int f[N],n,ne[N],m;
inline int Finds(int x)
{
int t = x;
while(x != f[x]) x = f[x];
f[t] = x;
return x;
}
inline void Union(int a,int b)
{
a = Finds(a),b = Finds(b);
f[a] = b;
}
inline void Init()
{
for(int i = 1;i <= n;++i) f[i] = i,ne[i] = i + 1;
}
inline void solve()
{
cin >> n >> m;
Init();
while(m--)
{
int op,a,b;
cin >> op >> a >> b;
if(op == 1) Union(a,b);
else if(op == 2)
{
int L = a,R = b;
int t = ne[L];
for(int i = L ;i <= R;i = t)
{
Union(i,R);
t = ne[i];
ne[i] = ne[R];
}
}else
{
if(Finds(a) != Finds(b)) NO;
else YES;
}
}
}
|
最后提交：
