# 2ms Union-Find and 21ms DFS

• 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) {
}
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) {
for (int neighbor : graph.get(key)) {
if (!set.contains(neighbor)) {
DFS(graph, set, neighbor);
}
}
}``````

• Great idea to count down from N. :)

also clever to let id point to it's grandparents

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

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