Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.*;
public class DisjointSet {
static class Edge{
int source;
int destination;
public Edge(int source, int destination) {
this.source = source;
this.destination = destination;
}
}
static class Graph{
int vertices;
LinkedList<Edge>[] adjList;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices){
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i <vertices ; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination){
Edge edge = new Edge(source, destination);
adjList[source].addFirst(edge);
allEdges.add(edge); //add to total edges
}
public void makeSet(int [] parent){
//Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i <vertices ; i++) {
parent[i] = i;
}
}
public int find(int [] parent, int vertex){
//chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
if(parent[vertex]!=vertex)
return find(parent, parent[vertex]);;
return vertex;
}
public void union(int [] parent, int x, int y){
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
//make x as parent of y
parent[y_set_parent] = x_set_parent;
}
public void disjointSets(){
//create a parent []
int [] parent = new int[vertices];
//makeset
makeSet(parent);
//iterate through all the edges and keep making the sets
for (int i = 0; i <allEdges.size() ; i++) {
Edge edge = allEdges.get(i);
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
//check if source vertex and destination vertex belongs to the same set
// if in same set then cycle has been detected else combine them into one set
if(x_set==y_set) {
//do nothing
}else
union(parent, x_set, y_set);
}
printSets(parent);
}
public void printSets(int [] parent){
//Find different Sets
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i <parent.length ; i++) {
if(map.containsKey(parent[i])){
ArrayList<Integer> list = map.get(parent[i]);
list.add(i);//add vertex
map.put(parent[i],list);
}else{
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
map.put(parent[i],list);
}
}
//Print the Different sets
Set<Integer> set = map.keySet();
Iterator<Integer> iterator = set.iterator();
while(iterator.hasNext()){
int key = iterator.next();
System.out.println("Set Id: " + key + " elements: " + map.get(key));
}
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1);
graph.addEgde(0, 2);
graph.addEgde(1, 3);
graph.addEgde(4, 5);
graph.disjointSets();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment