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:
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 edges
. Since all edges are undirected, [0, 1]
is the same as [1, 0]
and thus will not appear together in edges
.
public int countComponents(int n, int[][] edges) {
if(n < 1)
return 0;
if(edges.length == 0)
return n;
int[] union = new int[n];
Arrays.fill(union, -1);
for(int[] edge: edges){
if(edge[0] > edge[1])
swap(edge);
int b = edge[0], e = edge[1];
while(union[b] != -1){
b = union[b];
}
while(union[e] != -1){
e = union[e];
}
if(b != e){
union[e] = b;
n --;
}
}
return n;
}
private void swap(int[] edge){
int tmp = edge[1];
edge[1] = edge[0];
edge[0] = tmp;
}