jasonpogi1669

Disjoint Set | UNION and FIND using C++

Sep 1st, 2021 (edited)
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> parent;
  6.  
  7. int Find(int v) {
  8.     // traverse the tree structure in order to find the absolute root of a vertex
  9.     if (parent[v] == -1) {
  10.         return v;
  11.     }
  12.     return Find(parent[v]);
  13. }
  14.  
  15. void Union(int root_of_from, int root_of_to) {
  16.     // find the absolute roots of the two vertices again and change the absolute root
  17.     // of one vertex to the absolute root of the other vertex so they have the same absolute root
  18.     root_of_from = Find(root_of_from);
  19.     root_of_to = Find(root_of_to);
  20.     parent[root_of_from] = root_of_to;
  21. }
  22.  
  23. bool IsCyclic(vector<pair<int, int>>& edge_list) {
  24.     for (auto& p : edge_list) {
  25.         // find the absolute roots of the two vertices and check if it forms a cycle,
  26.         // then merge the vertices in one subset by making their absolute root the same
  27.         int root_of_from = Find(p.first);
  28.         int root_of_to = Find(p.second);
  29.         if (root_of_from == root_of_to) {
  30.             return true;
  31.         }
  32.         Union(root_of_from, root_of_to);
  33.     }
  34.     return false;
  35. }
  36.  
  37. int main() {
  38.     // input number of edges and vertices
  39.     int E, V;
  40.     cin >> E >> V;
  41.     // mark all vertices as separate subsets with only one (1) element
  42.     // and create the adjacency list based on the number of edges and vertices
  43.     parent.resize(V, -1);
  44.     vector<pair<int, int>> edge_list;
  45.     for (int i = 0; i < E; i++) {
  46.         int from, to;
  47.         cin >> from >> to;
  48.         edge_list.push_back(make_pair(from, to));
  49.     }
  50.     // check if the graph forms a cycle
  51.     if (IsCyclic(edge_list)) {
  52.         cout << "TRUE";
  53.     } else {
  54.         cout << "FALSE";
  55.     }
  56.     cout << '\n';
  57.     return 0;
  58. }
  59.  
Add Comment
Please, Sign In to add comment