Algorithms/Java/Graphs/DisjointSetUnion.java at main · Kumar-laxmi/Algorithms · 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
importjava.util.*;

classDisjointSetUnion {
staticint[] parent = newint[1000000];

// Find the root/representative of a vertex
staticintroot(inta) {
if (a == parent[a]) {
returna;
 }
// Path compression - Set the parent of 'a' to its root
returnparent[a] = root(parent[a]);
 }

// Connect two components by setting their parent
staticvoidconnect(inta, intb) {
a = root(a);
b = root(b);

if (a != b) {
// Union by setting the parent of 'b' to 'a'
parent[b] = a;
 }
 }

// Count the number of connected components
staticvoidconnectedComponents(intn) {
HashSet<Integer> s = newHashSet<Integer>();

for (inti = 0; i < n; i++) {
// Add the root of each vertex to the set
s.add(root(parent[i]));
 }
System.out.println("Number of connected components: " + s.size());
 }

staticvoidprintAnswer(intN, int[][] edges) {
// Initialize each vertex as its own parent
for (inti = 0; i <= N; i++) {
parent[i] = i;
 }
// Connect the edges
for (inti = 0; i < edges.length; i++) {
connect(edges[i][0], edges[i][1]);
 }
// Print the number of connected components
connectedComponents(N);
 }

publicstaticvoidmain(String[] args) {
Scannerscanner = newScanner(System.in);

System.out.print("Enter the number of vertices: ");
intN = scanner.nextInt();

System.out.print("Enter the number of edges: ");
intm = scanner.nextInt();

int[][] edges = newint[m][2];

System.out.println("Enter the edges:");
for (inti = 0; i < m; i++) {
edges[i][0] = scanner.nextInt();
edges[i][1] = scanner.nextInt();
 }

System.out.println("\nInput:");
System.out.println("Number of vertices: " + N);
System.out.println("Edges:");
for (inti = 0; i < m; i++) {
System.out.println(edges[i][0] + " " + edges[i][1]);
 }

System.out.println("\nOutput:");
printAnswer(N, edges);

scanner.close();
 }
}