547. Number of Provinces

time: O(edges*nodes) => 我想應該不是

t

space: O(n)

因為有環(has same root)就不能構成一個邊,

所以無環(x !=y)時, 可以成立一個邊, 也就會少掉一個 circle num

當 isConnected[i][j] == 1 => 去找是不是對應也是1 [j][i] 也就是利用 union find => 如果沒有circe => 代表有邊 .=> 代表是同一個group => res--

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

with path compression

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // use union find
        // so 0,0 is not
        if (isConnected == null || isConnected.length == 0) return 0;
        int res = isConnected.length;
        int n = isConnected.length;
        
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    res = union(roots, i, j, res);
                }
            } 
        }
        return res;
    }
    
    private int union(int roots[], int i , int j, int res) {
        int x = find(roots, i);
        int y = find(roots, j);
        if (x != y) {
            roots[x] = y;
            res--;
        }
        return res;
    }

    private int find(int roots[], int i) {
        while (roots[i] != i) {
            roots[i] = roots[roots[i]]; // add path compression
            i = roots[i];
        }
        return i;
    }
}

use Class

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

Solution 2: DFS

class Solution {
    public int findCircleNum(int[][] isConnected) {

        int[] visited = new int[isConnected.length]; // dont need init to 0
        int count = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (visited[i] == 0) {
                dfs(isConnected, visited, i);
                count++;
            }
        }
        return count;
    }

    public void dfs(int[][] isConnected, int[] visited, int i) {
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(isConnected, visited, j);
            }
        }
    }
}