首页 / 算法 / 一天一道算法题——朋友（并查集）
一天一道算法题——朋友（并查集）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了一天一道算法题——朋友（并查集），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3032字，纯文字阅读大概需要5分钟。
内容图文
题目背景
小明在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。
输出格式
一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）
输入输出样例
输入?4 3 4 2 1 1 1 2 2 3 1 3 -1 -2 -3 -3输出?
2
说明/提示
对于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数组优化并查集的存储。
内容总结
以上是互联网集市为您收集整理的一天一道算法题——朋友（并查集）全部内容，希望文章能够帮你解决一天一道算法题——朋友（并查集）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。