package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *  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 class _323 {

    public int countComponents(int n, int[][] edges) {
        if (n <= 1) {
            return n;
        }

        List<List<Integer>> adList = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            adList.add(new ArrayList<Integer>());
        }

        for (int[] edge : edges) {
            adList.get(edge[0]).add(edge[1]);
            adList.get(edge[1]).add(edge[0]);
        }

        for (List<Integer> list : adList) {
            for (int i : list) {
                System.out.print(i + ", ");
            }
            System.out.println();
        }

        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                Queue<Integer> q = new LinkedList<Integer>();
                q.offer(i);
                while (!q.isEmpty()) {
                    int index = q.poll();
                    visited[index] = true;
                    for (int j : adList.get(index)) {
                        if (!visited[j]) {
                            q.offer(j);
                        }
                    }
                }
            }
        }

        return count;
    }

}

@@ -138,16 +138,81 @@
 e;%0A%0A/**%0A
+ * 323. Number of Connected Components in an Undirected Graph%0A *%0A
  *  Give
@@ -838,17 +838,57 @@
  _323 %7B%0A
-%0A
+    public static class Solution1 %7B%0A%0A    
     publ
@@ -938,24 +938,28 @@
 ) %7B%0A        
+  
+  
 if (n %3C= 1) 
@@ -956,24 +956,28 @@
  (n %3C= 1) %7B%0A
+    
             
@@ -994,27 +994,34 @@
         
-%7D%0A%0A
+    %7D%0A%0A   
         
 List%3CLis
@@ -1012,16 +1012,17 @@
         
+ 
 List%3CLis
@@ -1056,29 +1056,16 @@
 rayList%3C
-List%3CInteger%3E
 %3E();%0A   
@@ -1061,32 +1061,36 @@
 st%3C%3E();%0A        
+    
 for (int i = 0; 
@@ -1111,24 +1111,28 @@
             
+    
 adList.add(n
@@ -1144,23 +1144,16 @@
 rayList%3C
-Integer
 %3E());%0A  
@@ -1150,35 +1150,43 @@
 t%3C%3E());%0A        
-%7D%0A%0A
+    %7D%0A%0A    
         for (int
@@ -1196,32 +1196,36 @@
 edge : edges) %7B%0A
+    
             adLi
@@ -1258,32 +1258,36 @@
 %5D);%0A            
+    
 adList.get(edge%5B
@@ -1304,35 +1304,43 @@
 ge%5B0%5D);%0A        
+   
+ 
 %7D%0A%0A
+    
         for (Lis
@@ -1371,32 +1371,36 @@
 ) %7B%0A            
+ 
+   
 for (int i : lis
@@ -1400,24 +1400,28 @@
 i : list) %7B%0A
+    
             
@@ -1456,34 +1456,41 @@
 %22);%0A            
-%7D%0A
+    %7D%0A   
             Syst
@@ -1477,32 +1477,33 @@
 %0A               
+ 
 System.out.print
@@ -1508,32 +1508,36 @@
 ntln();%0A        
+    
 %7D%0A%0A        boole
@@ -1531,16 +1531,20 @@
         
+  
+  
 boolean%5B
@@ -1571,16 +1571,20 @@
 ean%5Bn%5D;%0A
+    
         
@@ -1598,32 +1598,36 @@
 nt = 0;%0A        
+    
 for (int i = 0; 
@@ -1644,32 +1644,36 @@
 ) %7B%0A            
+   
+ 
 if (!visited%5Bi%5D)
@@ -1691,16 +1691,20 @@
         
+    
 count++;
@@ -1720,16 +1720,20 @@
         
+  
+  
 Queue%3CIn
@@ -1762,20 +1762,17 @@
 ist%3C
-Integer
 %3E();%0A
+    
     
@@ -1811,16 +1811,20 @@
         
+    
 while (!
@@ -1834,24 +1834,28 @@
 sEmpty()) %7B%0A
+    
             
@@ -1904,16 +1904,20 @@
         
+    
 visited%5B
@@ -1943,32 +1943,36 @@
                 
+  
+  
 for (int j : adL
@@ -1985,24 +1985,28 @@
 t(index)) %7B%0A
+    
             
@@ -2056,32 +2056,36 @@
                 
+    
 q.offer(j);%0A    
@@ -2080,16 +2080,46 @@
 fer(j);%0A
+                            %7D%0A
         
@@ -2190,27 +2190,21 @@
       %7D%0A
-    
+%0A
     
-%7D%0A%0A
         
@@ -2217,16 +2217,26 @@
  count;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 323