- Difficulty: Medium
iven
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:
0 3 | | 1 --- 2 4
Given
n = 5
and edges = [[0, 1], [1, 2], [3, 4]]
, return 2
.
Example 2:
0 4 | | 1 --- 2 --- 3
Given
n = 5
and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
, return 1
.
Note:
You can assume that no duplicate edges will appear in
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
.参考:https://discuss.leetcode.com/topic/32752/easiest-2ms-java-solution
Complexity: The complexity for M quick union + path compression on N objects should be N + MlgN, I think in this problem, M = 2E, N = V, so O(V + 2ElgV)
n
points =n
islands =n
trees =n
roots.- With each edge added, check which island is
e[0]
ore[1]
belonging to.- If
e[0]
ande[1]
are in same islands, do nothing.- Otherwise, union two islands, and reduce islands count by
1
.- Bonus: path compression can reduce time by
50%
.Hope it helps!
public class Solution { public int countComponents(int n, int[][] edges) { // initialize n isolated islands int[] roots = new int[n]; for(int i = 0; i < n; i++) roots[i] = i; int count =n; // perform union find for (int i = 0; i < edges.length; i++) { int root1 = findSet(roots,edges[i][0]);//when union, always update the top parent(recur) int root2 = findSet(roots,edges[i][1]); //if in one set means already reduce count by adding edge before, new edge not impact if(root1!=root2){ roots[root1] = root2;//in 2 sets,union(add a edge) count--; } } return count; } public int findSet(int[] roots,int i){ if(roots[i]==i)return i;//is top parent roots[i] = findSet(roots,roots[i]);//path compression(optional) return roots[i]; } }
Optional path compression: (Iteration has little difference from recursion)
public int findSet(int[] roots,int i){ while(roots[i] != i) { roots[i] = roots[roots[i]]; // optional: path compression i = roots[i]; } return i; }
No comments:
Post a Comment