🟡 剑指 Offer II 116. 省份数量

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

想到了某道题用parents的方法，学名叫做并查集。

关键在于如何合并parent节点，这里还是看了下题解：

class Solution {    public int findCircleNum(int[][] isConnected) {        int n = isConnected.length;        int[] parents = new int[n];
        for (int i=0; i<n; i+=1) {            parents[i] = i;        }
        for (int i=1; i<n; i+=1) {            for (int j=0; j<i; j+=1) {                if (isConnected[i][j] == 1) {                    union(parents, i, j);                }            }        }
        int res = n;        for (int i=0; i<n; i+=1) {            if (parents[i] != i) {                res -= 1;            }        }
        return res;    }
    private void union(int[] parents, int i, int j) {        parents[find(parents, i)] = find(parents, j);    }
    private int find(int[] parents, int i) {        if (parents[i] == i) {            return i;        }        parents[i] = find(parents, parents[i]);        return parents[i];    }}

题解2

用回传统的DFS咯

class Solution {    private void dfs(int[][] isConnected, boolean[] visited, int entry, int size) {        if (visited[entry]) {            return;        }        visited[entry] = true;        for (int i=0; i<size; i+=1) {            if (isConnected[entry][i] == 1) {                dfs(isConnected, visited, i, size);            }        }    }
    public int findCircleNum(int[][] isConnected) {        int n = isConnected.length;        boolean[] visited = new boolean[n];        int res = 0;
        for (int i=0; i<n; i+=1) {            if (!visited[i]) {                res += 1;                dfs(isConnected, visited, i, n);            }        }
        return res;    }}