一天一道算法题——朋友（并查集）

题目背景

小明在A公司工作，小红在B公司工作。

题目描述

这两个公司的员工有一个特点：一个公司的员工都是同性。

A公司有N名员工，其中有P对朋友关系。B公司有M名员工，其中有Q对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数(Xi,Yi)组成，表示朋友的编号分别为Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是1，小红的编号是-1.

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入格式

第1行，4个空格隔开的正整数N,M,P,Q。

之后P行，每行两个正整数Xi，Yi。

之后Q行，每行两个负整数Xi，Yi。

输出格式

一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出样例

输入

输出

说明/提示

对于30%数据，N,M<=100，P,Q<=200

对于80%数据，N,M<=4000,P,Q<=10000.

对于全部数据，N,M<=10000,P,Q<=20000。

这种题目一看就知道要用并查集做。

下面我们来看一下什么是并查集。

并查集：一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。基本操作有：初始化，合并和查找。

初始化：定义数组s

1 void init_set() {
2     for (int i = 1; i <= n; i++)
3         s[i] = i;
4 }

查找：找到该节点的根节点。(根据初始化，只要该节点为它本身，就代表它是根节点)

1 int find_set(int x) {
2     return x==s[x]?x:find_set(s[x]);
3 }

合并：

1 void union_set(int x, int y) {
2     x = find_set(x, f);
3     y = find_set(y, f);
4     if (x != y)
5         s[x] = y;
6 }

然后我们回到题目。

根据题目意思，我们定义两个数组a和b，一个a公司，一个b公司。

通过合并操作，我们可以很容易的把谁是谁的朋友给连接起来。

然后就是判断哪些人是小明，小红的朋友，通过两者根节点相等分别得出小明有朋友t1人，小红t2人

考虑到一夫一妻制，男生少那就配成t1对，女生少那就配成t2对。

取min就对了！

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, m, p, q,t1,t2;
 5 int a[10010], b[10010];
 6 
 7 void init_set() {
 8     for (int i = 1; i <= n; i++)
 9         a[i] = i;
10     for (int i = 1; i <= m; i++)
11         b[i] = i;
12 }
13 
14 int find_set(int x, bool f) {
15     if (f) {
16         if (a[x] != x)a[x] = find_set(a[x],f);
17         return a[x];
18     }
19     else {
20         if (b[x] != x)b[x] = find_set(b[x],f);
21         return b[x];
22     }
23 }
24 
25 void union_set(int x, int y, bool f) {
26     x = find_set(x, f);
27     y = find_set(y, f);
28     if (x != y)
29         if (f) 
30             a[x] = y;
31         else
32             b[x] = y;
33 }
34 
35 int main() {
36     cin >> n >> m >> p >> q;
37     init_set();
38     while (p--) {
39         cin >> t1 >> t2;
40         union_set(t1, t2,true);
41     }
42     while (q--) {
43         cin >> t1 >> t2;
44         union_set(-t1, -t2, false);
45     }
46     t1 = 0; t2 = 0;
47     p = find_set(1, true);
48     q = find_set(1, false);
49     for (int i = 1; i <= n; i++)
50         if (find_set(i,true) == p)
51             t1++;
52     for (int i = 1; i <= m; i++)
53         if (find_set(i,false) == q)
54             t2++;
55     cout << min(t1,t2);
56     return 0;
57 }

优化方面可以考虑快读；使用height数组优化并查集的存储。