【LeetCode每日一题】924. 尽量减少恶意软件的传播（并查集）
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
UnionFind uf = new UnionFind(n);//用并查集维护节点的连通关系
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (graph[i][j] == 1) {//如果存在连接
uf.union(i, j);//将节点i和节点j所在的集合合并
}
}
}
int ans = n;
int min = n;//最小结点
int max = 0;//最大感染数
int[] count = new int[n];
for (int x : initial) {
count[uf.find(x)]++;//统计每个初始感染节点所在集合的感染节点数量
min = Math.min(min, x);//更新最小节点
}
for (int x : initial) {
int root = uf.find(x);
if (count[root] == 1) {
int size = uf.size(root);
if (size > max || (size == max && x < ans)) {
// 如果当前集合的大小大于最大感染节点数，或者当前集合的大小等于最大感染节点数但节点值较小
ans = x;//更新答案为当前节点
max = size;//更新最大感染节点数
}
}
}
return ans == n ? min : ans;//ans==n说明没找到优化的方案，直接返回最小的结点。
}
}
class UnionFind {
//维护节点之间的连通关系
private final int[] p;//存储父结点
private final int[] size;//存储每个结点所在集合的大小
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;//把每个父结点设置为自己
size[i] = 1;//每个集合的初始大小为1
}
}
public int find(int x) {
//查找结点所在集合的根节点
if (p[x] != x) {
//如果父结点不是自己
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) { // 将两个节点所在的集合合并
int pa = find(a);
int pb = find(b);
if (pa == pb) {
//根节点相同，说明两个结点已经是在一个集合中了。
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;//将集合b连接到集合a上
size[pa] += size[pb];//更新集合a的大小
}else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
public int size(int root) {
获取指定根节点所在集合的大小
return size[root];
}
}