LeetCode [323] Number of Connected Components in an Undirected Graph

 323. Number of Connected Components in an Undirected Graph

Medium

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public int countComponents(int n, int[][] edges) { int[] p = new int[n]; for(int i=0; i<n; ++i) p[i] = i; for(int[] e : edges){ int u = e[0], v = e[1]; int x = find(u, p); int y = find(v, p); p[y] = x; } Set<Integer> group = new HashSet<>(); for(int i=0; i<n; ++i) group.add(find(i, p)); return group.size(); } int find(int x, int[] p){ while(x!=p[x]) return find(p[x], p); return x; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { int[][] matrix; int[] visited; int n; public int countComponents(int n, int[][] edges) { this.n = n; matrix = new int[n][n]; for(int[] e : edges){ int u = e[0], v = e[1]; matrix[u][v] = 1; matrix[v][u] = 1; } visited = new int[n]; int components = 0; for(int i=0; i<n; ++i){ if(visited[i]==0){ components++; dfs(i); } } return components; } void dfs(int node){ visited[node] = 1; for(int nxt = 0; nxt<n; nxt++){ if(matrix[node][nxt] == 1 && visited[nxt]==0){ dfs(nxt); } } } }