Java DFS & Union Find


  • 0

    Similar to 200.number of islands [https://leetcode.com/problems/number-of-islands/#/description](link url) this problem has two solutions:
    DFS:

    public class Solution {
        public int findCircleNum(int[][] M) {
            int N = M.length, count = 0;
            boolean[] visited = new boolean[N];
            for(int i = 0;i < N;i++){
                if(!visited[i]){
                    count++;
                    dfs(i, N, visited, M);
                }
            }
            return count;
        }
        private void dfs(int i, int N, boolean[] visited, int[][] M){
            visited[i] = true;
            for(int j = 0;j < N;j++){
                if(M[i][j] == 1 && !visited[j]){
                    dfs(j, N, visited, M);
                }
            }
        }
    }
    

    UnionFind:

    public class Solution {
        public int findCircleNum(int[][] M) {
            int N = M.length, count = N;
            int[] root = new int[N];
            for(int i = 0;i < N;i++){
                root[i] = i;
            }
           //remember we don't need to process duplicated edges
            for(int i = 0;i < N;i++){
                for(int j = i + 1;j < N;j++){
                    if(M[i][j] == 1){
                        int idi = findRoot(i, root), idj = findRoot(j, root);
                        if(idi != idj){
                            root[idi] = idj;
                            count--;
                        }
                    }
                }
            }
            return count;
        }
        int findRoot(int id, int[] root){
            while(id != root[id]){
                root[id] = root[root[id]];
                id = root[id];
            }
            return id;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.