文章目录
显示
? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。 |
?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
作者: Grey
原文地址:使用并查集解决的相关问题
关于并查集的说明,见如下博客:
相关题目
本题的解题思路参考博客
主要思路
横纵坐标表示的是城市,因为城市是一样的,所以只需要遍历对角线上半区或者下半区即可,如果某个(i,j)
位置是1
,可以说明如下两个情况
第一,i
这座城市和j
这座城市可以做union
操作。
第二,(j,i)
位置一定也是1。
遍历完毕后,返回整个并查集中的集合数量即可。
完整代码
public static int findCircleNum(int[][] m) {
int n = m.length;
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.setSize();
}
public static class UF {
int[] parent;
int[] help;
int[] size;
int sets;
public UF(int n) {
size = new int[n];
parent = new int[n];
help = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
sets = n;
}
public void union(int i, int j) {
if (i == j) {
return;
}
int p1 = find(i);
int p2 = find(j);
if (p2 != p1) {
int size1 = size[p1];
int size2 = size[p2];
if (size1 > size2) {
parent[p2] = p1;
size[p1] += size2;
} else {
parent[p1] = p2;
size[p2] += size1;
}
sets--;
}
}
public int find(int i) {
int hi = 0;
while (i != parent[i]) {
help[hi++] = i;
i = parent[i];
}
for (int index = 0; index < hi; index++) {
parent[help[index]] = i;
}
return i;
}
public int setSize() {
return sets;
}
}
待更新...
更多
转载请注明:xuhss » 使用并查集解决的相关问题