并查集相关
A Junk-Mail Filter 并查集删除 HDU2473
带删除的并查集操作。
如何删除：类似于虚拟节点的想法。每个点都有一个id，在并查集中用id操作。删一个点，就赋予该点一个新的id，这就相当于将该点原来的id设为虚拟节点。因为原id已经作废，指向原来的id的那些点就仍在同一个集合里。
1从原集合中删除，所以1下的0和2，3依然属于同一集合。1变为单独的一个节点。
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
| #include <cstdio>
#include <cstring>
#include <set>
int n,m;
const int maxn = 1e6+100;
int id[maxn],fa[maxn],vis[maxn];
int find(int u) {
return fa[u] = (fa[u]==u?u:find(fa[u]));
}
int main() {
int cnt = 0;
while(~scanf("%d%d",&n,&m)&&n+m) {
int t = n;
memset(vis,0,sizeof(vis));
for(int i = 0; i < n; ++i)
id[i] = fa[i] = i;
for(int i = 1; i <= m; ++i) {
char c; int u,v;
scanf("\n%c%d",&c,&u);
if(c != 'S') {
scanf("%d",&v);
fa[find(id[u])] = find(id[v]);
} else {
id[u] = n++; fa[id[u]] = id[u];
}
}
int tot = 0;
for(int i = 0; i < t; ++i)
if(!vis[find(id[i])])
vis[find(id[i])] = 1,++tot;
printf("Case #%d: %d\n",++cnt,tot);
}
return 0;
}
|
B Almost Union-Find 并查集删除+维护大小和总和 UVA11987
A题升级版，在删除的情况下维护集合大小和总和。因为要这样维护，所以在合并的时候要判断u和v必须不在在同一集合
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
| #include <cstdio>
int n,m;
const int maxn = 3e5+100;
int fa[maxn],sz[maxn],id[maxn];
typedef long long ll;
ll sum[maxn];
int find(int u) {
return fa[u] = (fa[u] == u)?u:find(fa[u]);
}
inline void merge(int u,int v) {
int a = find(id[u]),b = find(id[v]);
if(a == b) return;
sum[b] += sum[a];
sz[b] += sz[a];
fa[a] = b;
}
inline void erase(int u) {
if(sz[find(id[u])] == 1) return;
sum[find(id[u])] -= u,--sz[find(id[u])];
id[u] = ++n,fa[id[u]] = id[u],sum[id[u]] = u,sz[id[u]] = 1;
}
int main() {
while(~scanf("%d%d",&n,&m)) {
int t = n;
for(int i = 1; i <= n; ++i)
fa[i] = id[i] = i,sz[i] = 1,sum[i] = i;
for(int i = 1; i <= m; ++i) {
int c,u,v;
scanf("%d",&c);
if(c == 1) {
scanf("%d%d",&u,&v);
merge(u,v);
} else if(c == 2) {
scanf("%d%d",&u,&v);
if(find(id[u]) == find(id[v])) continue;
erase(u);
merge(u,v);
} else {
scanf("%d",&u);
printf("%d %d\n",sz[find(id[u])],sum[find(id[u])]);
}
}
}
return 0;
}
|
D A Bug’s Life 带权并查集
此题是食物链弱化版。
带权并查集主要是合并：如何处理边权。
当然如果A+C-B<0也无所谓，大不了建负边。
以及并查集边权在压缩路径时也要维护，这个好好看就行。
在此题中w==1，以及dist[v] - dist[u] + 1也不会<0,当然如果是食物链那题估计要+3%3保持不为负吧
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
| #include <cstdio>
int fa[2048],dist[2048];
int n,m;
int find(int u) {
if(u == fa[u]) return u;
int f = find(fa[u]);
dist[u] = (dist[fa[u]] + dist[u]) % 2;
fa[u] = f;
return fa[u];
}
int abs(int u) {
if(u < 0) return -u;
return u;
}
int main() {
int T; scanf("%d",&T);
int cnt = 0;
while(T--) {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)
fa[i] = i,dist[i] = 0;
bool fault = 0;
while(m--) {
int u,v;
scanf("%d%d",&u,&v);
if(u == v) continue;
int f1 = find(u),f2 = find(v);
if(f1 == f2) {
if(dist[u]%2 == dist[v]%2) fault = 1;
} else {
int f1 = find(u),f2 = find(v);
dist[f1] = (dist[v] - dist[u] + 1)%2;
fa[f1] = f2;
}
}
printf("Scenario #%d:\n",++cnt);
if(fault) puts("Suspicious bugs found!\n");
else puts("No suspicious bugs found!\n");
}
return 0;
}
|
E Restructuring Company 并查集维护区间 CF566D
非常神奇的思想：首先用next数组记录该点所在的区间中最右边不属于此区间的第一个节点。假设区间15，那么next[15] = 6;
也就是说，从inext[i]-1的所有点都和i在同一个区间。所以在完成i的合并操作后，inext[i]-1都完成了此合并操作，所以可以跳到next[i]继续合并。
这个next有点类似于kmp里的next？
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
| #include <cstdio>
#include <algorithm>
const int maxn = 2e5+100;
int fa[maxn],next[maxn];
int n,q;
int find(int u) {
return fa[u] = (fa[u]==u)?u:find(fa[u]);
}
void Merge(int u,int v) {
fa[find(u)] = find(v);
}
int main() {
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; ++i)
fa[i] = i,next[i] = i+1;
while(q--) {
int type,u,v;
scanf("%d%d%d",&type,&u,&v);
if(type == 1) {
Merge(u,v);
} else if(type == 2) {
int t;
for(int i = u+1; i <= v; ) {
Merge(i,i-1);
t = next[i];
next[i] = next[v];
i = t;
}
} else {
if(find(u) == find(v)) puts("YES");
else puts("NO");
}
}
return 0;
}
|
H Virtual Friends 并查集维护集合大小
维护并查集的集合大小。方法是开一个size数组，很简单所以看看代码应该就会懂。
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
| #include <cstdio>
#include <iostream>
#include <string>
#include <map>
const int maxn = 2e5+10;
int fa[maxn],size[maxn];
int scnt = 0;
int find(int u) {
return fa[u] = (fa[u]!=u)?find(fa[u]):u;
}
int main() {
int T;
while(~scanf("%d",&T)) {
while(T--) {
std::map<std::string,int> p;
scnt = 0;
for(int i = 0; i < maxn; ++i)
fa[i] = i,size[i] = 1;
int f; scanf("%d",&f);
for(int i = 1; i <= f; ++i) {
std::string a,b;
std::cin>>a>>b;
if(p[a] == 0) p[a] = ++scnt;
if(p[b] == 0) p[b] = ++scnt;
int f1 = find(p[a]),f2 = find(p[b]);
if(f1 != f2) {
size[f2] += size[f1];
fa[f1] = f2;
}
printf("%d\n",size[f2]);
}
}
}
return 0;
}
|
I Asya And Kittens CF1131F 并查集维护区间
题意：一个长度为n的序列，最初每个元素存在于只属于自己的一个集合。经过n-1次合并后所有元素都属于同一集合。给出n-1次合并，让你还原之前的序列，答案不唯一。
方法是用并查集维护一个区间并记录该区间的left和right。然而直接写第八个点会tle。需要保证让长度短的区间合并到长度长的区间，原因不明。。。
这个题解好像没用swap
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
| #include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
const int maxn = 2e5;
std::vector<int> G[maxn];
int set[maxn],pre_set[maxn],nxt_set[maxn];
int pre_p[maxn],nxt_p[maxn];
int len[maxn];
int find(int u) {
return set[u]==u?u:find(set[u]);
}
int main() {
int n; scanf("%d",&n);
for(int i = 1; i <= n; ++i)
set[i] = pre_set[i] = nxt_set[i] = i,pre_p[i] = nxt_p[i] = -1,len[i] = 1;
for(int i = 1; i < n; ++i) {
int u,v; scanf("%d%d",&u,&v);
u = find(u),v = find(v);
if(len[u] > len[v]) std::swap(u,v);
nxt_p[nxt_set[u]] = pre_set[v];
pre_p[pre_set[v]] = nxt_set[u];
pre_set[v] = pre_set[u];
len[v] += len[u];
set[u] = v;
}
bool fir = 1;
for(int i = pre_set[find(1)]; i != -1; i = nxt_p[i]) {
if(!fir) printf(" ");
else fir = 0;
printf("%d",i);
}
return 0;
}
|