Disjoint Set (Union-Find)

Posted on | Edited on | Views:

link

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
81
82
83
// import java.util.*;
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;
        ArrayList<Edge> allEdges;

        Graph(int vertices) {
            this.vertices = vertices;
            allEdges = new ArrayList<>();
        }

        public void addEgde(int source, int destination) {
            Edge edge = new Edge(source, destination);
            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 boolean isCycle() {
            // 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) return true;
                else union(parent, x_set, y_set);
            }
            // if here, means cycle was not found
            return false;
        }
    }
}
/*
public class MyClass {
    public static void main(String[] args) {
        int vertices = 6;
        DisjointSet.Graph graph = new DisjointSet.Graph(vertices);
        graph.addEgde(0, 1);
        graph.addEgde(0, 2);
        graph.addEgde(1, 3);
        graph.addEgde(3, 4);
        graph.addEgde(2, 3);
        graph.addEgde(4, 5);
        System.out.println("Graph contains cycle: " + graph.isCycle());
    }
}*/
0%