并查集
发表于|更新于
|字数总计:1.5k|阅读时长:5分钟|阅读量:
并查集
在讲并查集之前,我们先思考一个问题,假设幼儿园小班有六个小朋友,分别为小a,小b,小c,小d,小e,小f,
但并不是每个人都是朋友, 我们规定朋友的朋友也是朋友,例如小a和小b是朋友,小b和小c也是朋友,那么小c和
小a同样也是朋友。现在要求一共有几个朋友圈。 已知小a和小b是朋友,小d和小e是朋友,小e和小f是朋友。我们很
容易能够确认小a和小b是一个朋友圈,小d,小e以及小f是一个朋友圈,而小c自己一个人一个朋友圈。
因为人数很少,我们能够很轻易地判断有几个朋友圈,但当人数很多的时候呢,我们不能每个都去遍历,去数有多少
个朋友圈。这就需要我们本次的知识——并查集。
并查集我们通过构建树状结构来实现,在这里我们分析上面的例子,首先在条件未知的情况下,我们让每个人都自己
一个人为一个朋友圈,如下图:
在初始情况下,每个小朋友自己一个人为一个朋友圈,在上面我们说了,并查集通过树状结构实现,所以就需要根节点,
初始状态下,根结点就是他们本身。现在我们接入第一个条件,即小a和小b是朋友,能够确认的是把小a和小b连接起来,
但问题是如何连接——答案是分别寻找他们的根节点,然后把他们的根节点连接起来,并且把其中一个根节点当作另一个根节点的父节点.
这也即使并查集的思想。所以这里我们要把小a和小b的根节点起来,并且把小b的根节点作为小a根节点新的子节点,如下图:
看到这里的时候,有人会想,随着人数增多,如何找到他们的根节点呢?这里就需要引进一个find()函数来寻找他们的根节点,
而find()的目的就是为了查询他们的根节点,具体如下:
1 2 3 4 5 6
| int find(int x) { if (pre[x] == x) return x; return find(pre[x]); }
|
上面的find()的代码,如果pre[x]的根节点等于它本身,则返回它本身,如果不是,则返回find(pre[x]),通过
继续递归函数,获得最终的根节点。
查找根节点有find()函数,那么把两个节点连接在一起,同样有一个合并函数merge(),find()函数和merge()函数
是并查集具备的两大操作,merge()函数如下:
1 2 3 4
| void merge(int i, int j) { fa[find(i)] = find(j); }
|
merge()函数很简单,只需要把一个节点的根节点等于另一个根节点即可。
所有的关系都引入之后,朋友圈状况如下:
上面就是并查集的主要思想,下面看一个例子:
题目描述
班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,
那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。
给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果 M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,
否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
分析: 很明显这就是一个并查集的问题,并且与我们的例子很相似,只不过这里使用矩阵来表示谁和谁是朋友,具体代码
如下:
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
|
using namespace std;
// 初始化并查集,每个元素自己就是一个集合 vector<int> initUnionFind(int n) { vector<int> parent(n); for (int i = 0; i < n; ++i) { parent[i] = i; // 初始时,每个节点的父节点是自己 } return parent; }
// 查找元素x的根节点 int findRoot(vector<int>& parent, int x) { if (parent[x] != x) { parent[x] = findRoot(parent, parent[x]); // 路径压缩,直接让x的父节点变为根节点 } return parent[x]; }
// 合并元素x和元素y所在的集合 void unite(vector<int>& parent, int x, int y) { int rootX = findRoot(parent, x); int rootY = findRoot(parent, y); if (rootX != rootY) { parent[rootX] = rootY; // 将x的根节点的父节点设为y的根节点,实现集合合并 } }
// 计算并查集中集合的个数 int countCircles(vector<int>& parent, int n) { int count = 0; for (int i = 0; i < n; ++i) { if (findRoot(parent, i) == i) { ++count; // 如果i是根节点,说明它是一个独立的集合 } } return count; }
// 主函数,计算朋友圈总数 int findCircleNum(vector<vector<int>>& M) { int N = M.size(); vector<int> parent = initUnionFind(N); // 初始化并查集
// 遍历矩阵M,合并朋友关系对应的节点 for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (M[i][j] == 1) { unite(parent, i, j); // 如果i和j是朋友,合并他们所在的集合 } } }
// 计算并查集中集合的个数,即朋友圈的总数 return countCircles(parent, N); }
int main() { int N; cin >> N;
vector<vector<int>> M(N, vector<int>(N, 0)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> M[i][j]; } }
int numCircles = findCircleNum(M); cout << numCircles << endl;
return 0; }
|
关于并查集的知识就到这里,有什么问题请打在评论区,谢谢!