种类并查集（反集）

[BOI2003]团伙

题目描述

现在有 $n$ 个人，他们之间有两种关系：朋友和敌人。我们知道：

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 $n$ 代表人数。

第二行输入一个整数 $m$ 表示接下来要列出 $m$ 个关系。

接下来 $m$ 行，每行一个字符 $opt$ 和两个整数 $p,q$，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 $opt$ 有两种可能：

• 如果 $opt$ 为 F，则表明 $p$ 和 $q$ 是朋友。
• 如果 $opt$ 为 E，则表明 $p$ 和 $q$ 是敌人。

输出格式

一行一个整数代表最多的团体数。

样例 #1

样例输入 #1

6
4
E 1 4
F 3 5
F 4 6
E 1 2
1
2
3
4
5
6

样例输出 #1

3
1

提示

对于 $100\%$ 的数据，$2\le n\le 1000$，$1\le m\le 5000$，$1\le p,q\le n$。

---

题意很不清楚。样例解释{1},{2,4,6},{3,5}。凑合理解吧，是朋友的必须一个集合，也可以单独一个集合

注意：朋友的敌人不是敌人，敌人的朋友不是敌人。

两种写法：

1. 记录每个人的敌人。

int n,fa[N],m;
int e[N];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}

int main()
{
    cin>>n>>m;
    fo(i,1,n)fa[i]=i;
    fo(i,1,m){
        char c;int a,b;
        cin>>c>>a>>b;
        if(c == 'E'){
            if(!e[a]){
                e[a] = b;
            }
            if(!e[b]){
                e[b] = a;
            }
            merge(a,e[b]);
            merge(b,e[a]);
        }
        else{
            merge(a,b);
        }
    }
    int ans=0;
    fo(i,1,n)if(fa[i] == i)ans++;
    cout<<ans;
	return 0;
}
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

2. 构建反集（其实超好理解）

如果a和b是敌人，合并n+b和a，n+a和b
如果a和c是敌人，合并n+c和a，n+a和c
那么b和c就并在一起了
这样就符合了题目敌人的敌人是朋友的规则
1
2
3
4

const int N = 4e5+10;
int p[N];
int n,m;
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=2*n;i++) p[i] = i;
        int a,b;
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            p[find(a+n)] = find(b);
            p[find(b+n)] = find(a);
        }
        int ans = 0;
        for(int i=1;i<=n;i++) if(p[i] == i) ans++;
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

所以这个解决了一个限制连边求集合题目的一种解法。

E. Split Into Two Sets (学习T宝代码)

我的
#pragma GCC optimize(2)
#include
using namespace std;
const int N = 4e5+10;
int p[N];
int d[N];
int n,m;
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        memset(d,0,sizeof d);
        for(int i=1;i<=2*n;i++) p[i] = i;
        int a,b;
        bool ok = 1;
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            d[a]++;
            d[b]++;
            p[find(a+n)] = find(b);
            p[find(b+n)] = find(a);
        }
        int ans = 0;
        for(int i=1;i<=n;i++){
        	if(d[i]>2){
        		ok = 0;
        		break;
        	}
        	if(find(i) == find(i+n)){
        		ok = 0;
        		break;
        	}
        }
        cout<<(ok ? "YES" : "NO") <<endl;
    }
    return 0;
}

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

/**
 *    author:  tourist
 *    created: 10.07.2022 18:40:44       
**/
#include 

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> deg(n);
    dsu d(2 * n);
    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      --x; --y;
      deg[x] += 1;
      deg[y] += 1;
      d.unite(x, y + n);
      d.unite(x + n, y);
    }
    bool ok = true;
    for (int i = 0; i < n; i++) {
      if (deg[i] > 2) {
        ok = false;
      }
      if (d.get(i) == d.get(i + n)) {
        ok = false;
      }
    }
    cout << (ok ? "YES" : "NO") << '\n';
  }
  return 0;
}

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

我竟然也能看懂T宝代码了qwq，T宝缩进是两格

class dsu {
    public: 
    vector<int> p;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0); // 从0开始个p赋值。
    }

    inline int get(int x) {
        return (x == p[x] ? x : (p[x] = get(p[x])));
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            p[x] = y;
            return true;
        }
        return false;
    }
};
初始化的方法：dsu d(2 * n);
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