Graph/Disjoint Set.java at master · golumall/Graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.Scanner;
import java.util.Set;
import java.util.HashMap;
import java.util.Map;
class DisjointSet
{
	Map<Long,Node> mp=new HashMap<>();
	class Node
	{
	long data;
	Node parent;
	int rank;
	}
	//Create Set with Only One Element
	public void makeSet(long data)
	{
		Node node=new Node();
		node.data=data;
		node.parent=node;
		node.rank=0;
		mp.put(data,node);
	}
	public boolean union(long data1,long data2)
	{
		Node node1=mp.get(data1);
		Node node2=mp.get(data2);

		Node parent1=findSet(node1);
		Node parent2=findSet(node2);

		if(parent1.data==parent2.data)
			return false;
		if(parent1.rank>=parent2.rank)
		{
			parent1.rank=(parent1.rank==parent2.rank)?parent1.rank+1:parent1.rank;
			parent2.parent=parent1;
		}
		else
			parent1.parent=parent2;
		return true;
	}
	public long findSet(long data)
	{
		return findSet(mp.get(data)).data;
	}
	public Node findSet(Node node)
	{
		Node parent=node.parent;
		if(parent==node)
			return parent;
		node.parent=findSet(node.parent);
		return node.parent;
	}
public static void main(String[] args) {
	DisjointSet ds=new DisjointSet();
	ds.makeSet(1);
	ds.makeSet(2);
	ds.makeSet(3);
	ds.makeSet(4);
	ds.makeSet(5);
	ds.makeSet(6);
	ds.makeSet(7);

	ds.union(1,2);
	ds.union(2,3);
	ds.union(4,5);
	ds.union(5,6);
	ds.union(6,7);
	ds.union(3,7);
	System.out.println(ds.findSet(1));
	System.out.println(ds.findSet(2));
	System.out.println(ds.findSet(3));
	System.out.println(ds.findSet(4));
	System.out.println(ds.findSet(5));
	System.out.println(ds.findSet(6));
	System.out.println(ds.findSet(7));


}
}