547. Number of Provinces

use BFS

time: O(n^2), matrix size

space: O(n), use queue & visited array

class Solution {
    public int findCircleNum(int[][] isConnected) {
        boolean visited[] = new boolean[isConnected.length];
        
        int count = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (visited[i] == false) {
                count++;
                BFS(i, isConnected, visited);
            }
        }
        return count;
    }
    
    private void BFS(int beginCity, int[][] isConnected, boolean visited[]) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginCity);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cityNo = queue.poll();
                visited[cityNo] = true;
                
                for (int otherCityNo = 0; otherCityNo < isConnected[0].length; otherCityNo++) {
                    if (visited[otherCityNo] == false && isConnected[cityNo][otherCityNo] == 1) {
                        queue.offer(otherCityNo);
                    }
                }
            }
        }
    }
}

don't use visited array, just set isConnected[][] = 2 as visited, but space is still O(n)

class Solution {
    public int findCircleNum(int[][] isConnected) {
        
        int count = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (isConnected[i][i] == 1) {
                count++;
                BFS(i, isConnected);
            }
        }
        return count;
    }
    
    private void BFS(int beginCity, int[][] isConnected) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginCity);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cityNo = queue.poll();
                isConnected[cityNo][cityNo] = 2;
                
                for (int otherCityNo = 0; otherCityNo < isConnected[0].length; otherCityNo++) {
                    if (isConnected[otherCityNo][otherCityNo] == 1 && isConnected[cityNo][otherCityNo] == 1) {
                        queue.offer(otherCityNo);
                    }
                }
            }
        }
    }
}

another way is to use union find

union find

time: O(n^2), matrix size

space: O(n), union find map size

/*
[1,1,0],
[1,1,0],
[0,0,1]]
*/
class Solution {
    public int findCircleNum(int[][] isConnected) {
        if (isConnected == null || isConnected.length == 0) {
            return 0;
        }
        UnionFind uf = new UnionFind();
        int m = isConnected.length;
        int n = isConnected[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.add(i); // 無向圖, 必須做雙向
                    uf.add(j);
                    uf.union(i, j);
                }
            }
        }
        return uf.getNumOfSet();
    }
}

class UnionFind {
    private Map<Integer, Integer> parent;
    private int numOfSet = 0;
    UnionFind() {
        this.parent = new HashMap<>();
    }
    public void add(int x) {
        if (parent.containsKey(x)) {
            return;
        }
        parent.put(x, null);
        numOfSet++;
    }
    public int find(int x) {
        int root = x;
        while (parent.get(root) != null) {
            root = parent.get(root);
        }
        
        while (x != root) {
            int xParent = parent.get(x);
            parent.put(x, root);
            x = xParent;
        }
        return root;
    }
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent.put(rootX, rootY);
            numOfSet--;
        }
    }
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    public int getNumOfSet() {
        return numOfSet;
    }

}