A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset. Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...
Comments
Post a Comment