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;

 }

results matching ""

    No results matching ""