Java Three Methods, DFS, BFS, UnionFind (union by rank and path compression)


  • 0

    DFS:

        private void dfs(int i, LinkedList<Integer>[] adj, boolean[] marked) {
            marked[i] = true;
            for (int j : adj[i]) {
                if (!marked[j]) dfs(j, adj, marked);
            }
        }
        public int findCircleNum(int[][] M) {
            int n = M.length, count = 0;
            LinkedList<Integer>[] adj = new LinkedList[n];
            for (int i = 0; i < n; i++) adj[i] = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (M[i][j] == 1) {
                        adj[i].add(j);
                        adj[j].add(i);
                    }
                }
            }
            boolean[] marked = new boolean[n];
            for (int i = 0; i < n; i++) {
                if (!marked[i]) {
                    dfs(i, adj, marked);
                    count++;
                }
            }
            return count;
        }
    

    BFS:

        public int findCircleNum(int[][] M) {
            int n = M.length, count = 0;
            LinkedList<Integer>[] adj = new LinkedList[n];
            for (int i = 0; i < n; i++) adj[i] = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (M[i][j] == 1) {
                        adj[i].add(j);
                        adj[j].add(i);
                    }
                }
            }
            boolean[] marked = new boolean[n];
            for (int i = 0; i < n; i++) {
                if (marked[i]) continue;
                count++;
                LinkedList<Integer> queue = new LinkedList<>();
                marked[i] = true;
                queue.add(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    for (int k : adj[j]) {
                        if (!marked[k]) {
                            marked[k] = true;
                            queue.add(k);
                        }
                    }
                }
            }
            return count;
        }
    

    Union Find:

        private int[] parent, rank;
        private int count;
        private int find(int x) {
            int i = x;
            while (parent[i] != i) i = parent[i];
            while (x != i) {
                int tmp = parent[x];
                parent[x] = i;
                x = tmp;
            }
            return i;
        }
        private void union(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return;
            count--;
            if (rank[x] == rank[y]) {
                parent[py] = px;
                rank[px]++;
            } else if (rank[x] > rank[y]) {
                parent[py] = px;
            } else {
                parent[px] = py;
            }
        }
        public int findCircleNum(int[][] M) {
            int n= M.length;
            count = n;
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
            for (int i = 0; i < n; i++) {
                for (int j = i+1; j < n; j++) {
                    if (M[i][j] == 1) union(i, j);
                }
            }
            return count;
        }
    

Log in to reply
 

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