@@ -0,0 +1,2273 @@
+package algorithms.problems;%0A%0Aimport java.util.HashSet;%0Aimport java.util.Set;%0A%0Aimport datastructures.disjointsets.DisjointSetWithPathCompression;%0Aimport datastructures.graph.AbstractGraph;%0Aimport datastructures.graph.UndirectedGraph;%0Aimport datastructures.graph.Vertex;%0A%0Apublic class ConnectedComponents %7B%0A%0A  private DisjointSetWithPathCompression%3CVertex%3CInteger%3E%3E disjointSet = null;%0A  private AbstractGraph%3CInteger%3E graph = null;%0A%0A  public ConnectedComponents() %7B%0A    disjointSet = new DisjointSetWithPathCompression%3CVertex%3CInteger%3E%3E();%0A    graph = new UndirectedGraph%3CInteger%3E();%0A  %7D%0A%0A  public void constructGraph(String%5B%5D input) %7B%0A    for (String line : input) %7B%0A      String%5B%5D values = line.split(%22 %22);%0A      String action = values%5B0%5D;%0A      Vertex%3CInteger%3E sourceVertex = null, destVertex = null;%0A      switch (action) %7B%0A      case %22vertex%22:%0A        Vertex%3CInteger%3E vertex = graph.createVertex(Integer.parseInt(values%5B1%5D));%0A        if (vertex != null) %7B%0A          disjointSet.makeSet(vertex);%0A          System.out.println(%22Created Vertex with label: %22 + values%5B1%5D);%0A        %7D else %7B%0A          System.out.println(%22Vertex creation failed for label: %22 + values%5B1%5D);%0A        %7D%0A        break;%0A      case %22edge%22:%0A        sourceVertex = graph.getVertex(Integer.parseInt(values%5B1%5D));%0A        destVertex = graph.getVertex(Integer.parseInt(values%5B2%5D));%0A        if (graph.addEdge(sourceVertex, destVertex)) %7B%0A          disjointSet.union(sourceVertex, destVertex);%0A          System.out.println(%22Edge created between: %22 + values%5B1%5D + %22 and %22 + values%5B2%5D);%0A        %7D else %7B%0A          System.out.println(%22Either of the vertices dont exist%22);%0A        %7D%0A        break;%0A      %7D%0A    %7D%0A  %7D%0A%0A  public Set%3CInteger%3E connectedComponents() %7B%0A    Set%3CInteger%3E componentSet = new HashSet%3CInteger%3E();%0A    Set%3CVertex%3CInteger%3E%3E vertices = graph.verticesSet();%0A%0A    for (Vertex%3CInteger%3E vertex : vertices) %7B%0A      componentSet.add(disjointSet.findSet(vertex).label);%0A    %7D%0A%0A    return componentSet;%0A  %7D%0A%0A  public boolean sameComponent(String value1, String value2) %7B%0A    Vertex%3CInteger%3E vertex1 = graph.getVertex(Integer.parseInt(value1));%0A    Vertex%3CInteger%3E vertex2 = graph.getVertex(Integer.parseInt(value2));%0A%0A    return disjointSet.findSet(vertex1).equals(disjointSet.findSet(vertex2));%0A  %7D%0A%7D%0A

Add ConnectedComponents implementation using disjoint sets