924. Minimize Malware Spread

Version #2 Brute Force DFS/BFS[TODO]

Version #1 Union Find
Trick part is if two initial ids belong to the same component, then remove either of them would be meaningless
So we need to make sure that our initial point is the only initial point in its component
We make a count of root(init) to see how many initial points are under this current root
And then if the size of this root is max, we record the id
1 edge case is that if we can't find any count[root(init)] == 1 -> means all initial points belong to one component -> in this scenario we need to return minimum id among all initial ids

97.32 %
class Solution {
    private int[] id;
private int[] size;
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][j] == 1) {
union(i, j);
}
}
}
int[] count = new int[N];
for (int init : initial) {
count[root(init)]++;
}
int resultCount = -1;
Integer resultId = null;
int minId = N;
for (int init : initial) {
minId = Math.min(minId, init);
int root = root(init);
if (count[root] == 1) {
if (size[root] >= resultCount) {
resultCount = size[root];
resultId = (resultId == null) ? init : Math.min(resultId, init);
}
}
}
return resultCount == -1 ? minId : resultId;
}
private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
}