kuangbin专题十---并查集

ACM

并查集专题

B

模板题，我他妈的wa了一万发，后来发现有东西变化了。。。

AC code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
const int maxn = 3e4+10;
int fa[maxn];
int num[maxn];
int find_fa(int x){
    int a = x;
    while(x!=fa[x]){
        x = fa[x];
    }
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void uni(int u, int v){
    int fau = find_fa(u);
    int fav = find_fa(v);
    if(fau!=fav)fa[fau] = fav;
}
void init(){
    for(int i=0; i<maxn; i++) fa[i] = i;
}
int main(){
    while(scanf("%d%d", &n, &m)!=EOF&&(n||m)){
        int k;
        init();
        for(int i=0; i<m; i++){
            scanf("%d", &k);
            for(int j=0; j<k; j++){
                scanf("%d", &num[j]);
            }
            for(int j=1; j<k; j++){
                uni(num[0], num[j]);
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            find_fa(i);
        }
        //这个一开始写在了前面，可能会被修改。。。所以一直错
        int father = fa[0];
        for(int i=0; i<n; i++){
            if(fa[i] == father) ans++;
        }
        printf("%d\n", ans);
    }
}

E食物链

有两个教训：

  1. 只有一组数据的时候，不要用eof来判断
  2. 老老实实用scanf来读取数据，关同步照样会超时的。

题解

划分为三个集合，若有关系，那么就在集合之间连一条边。

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 <cstdio>
#include <cstring>
#include<queue>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5e4+10;
int fa[maxn*3+10];
int find_fa(int x){
    int a = x;
    while(x!=fa[x]){
        x = fa[x];
    }
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void uni(int u, int v){
    int fau = find_fa(u);
    int fav = find_fa(v);
    fa[fau] = fav;
}
void init(){
    for(int i=0; i<maxn*3; i++) fa[i] = i;
}
bool same(int u, int v){
    int fau = find_fa(u);
    int fav = find_fa(v);
    return fau==fav?true:false;
}
int n, k;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    {
        init();
        int ans = 0;
        int op, a, b;
        for(int i=0; i<k; i++){
            cin>>op>>a>>b;
            if(a>n||b>n){
                ans++;
                continue;
            }
            else if(op == 2&&a == b){
                ans++;
                continue;
            }
            if(op == 1){
                if(same(a, b+n)||same(a, b+2*n)){
                    ans++;
                    continue;
                }
                uni(a, b);
                uni(a+n, b+n);
                uni(a+2*n, b+2*n);
            }
            else{
                if(same(a, b)||same(a, b+2*n)){
                    ans++;
                    continue;
                }
                uni(a, b+n);
                uni(a+n, b+2*n);
                uni(a+2*n, b);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

未解决的问题

本文标题:kuangbin专题十---并查集

文章作者:Babydragon

发布时间:2018-05-14, 20:51:11

最后更新:2018-05-15, 13:35:47

原始链接:http://baolintian.github.io/2018/05/14/kuangbin专题十-并查集/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. B
    1. 1.1. AC code
  2. 2. E食物链
    1. 2.1. 题解
    2. 2.2. AC代码
  3. 3. 未解决的问题
{{ live2d() }}