2ms Union-Find and 21ms DFS


  • 4
    M

    Union-Find: basic idea is that initially we have n components, if two node have different id, we unites them, and the number of components would decrease by one.

           public int countComponents(int n, int[][] edges) {
                int[] id = new int[n];
                for (int i = 0; i < n; i++) {
                    id[i] = i;
                }
                int res = n;
                for (int[] edge : edges) {
                    if (unite(edge[0], edge[1], id)) {
                        res--;
                    }
                }
                return res;
            }
            private boolean unite(int p, int q, int[] id) {
                int pId = find(p, id);
                int qId = find(q, id);
                if (pId == qId) {
                    return false;
                } else {
                    id[pId] = qId;
                    return true;
                }
            }
            private int find(int p, int[] id) {
                while (id[p] != p) {
                    id[p] = id[id[p]];
                    p = id[p];
                }
                return p;
            }
    

    DFS:

       public int countComponents(int n, int[][] edges) {
            HashMap<Integer, List<Integer>> graph = new HashMap();
            for (int i = 0; i < n; i++) {
                graph.put(i, new ArrayList<Integer>());
            }
            for (int[] edge : edges) {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
            HashSet<Integer> set = new HashSet();
            int res = 0;
            for (int i = 0; i < n; i++) {
                if (!set.contains(i)) {
                    res++;
                    DFS(graph, set, i);
                }
            }
            return res;
        }
        private void DFS(HashMap<Integer, List<Integer>> graph, HashSet<Integer> set, int key) {
            set.add(key);
            for (int neighbor : graph.get(key)) {
                if (!set.contains(neighbor)) {
                    DFS(graph, set, neighbor);
                }
            }
        }

  • 0
    Z

    Great idea to count down from N. :)

    also clever to let id point to it's grandparents

    id[p] = id[id[p]];

Log in to reply
 

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