Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct node {
- int parent;
- int rank;
- };
- vector<node> dsuf;
- int Find(int v) {
- // traverse the tree structure and apply path compression
- if (dsuf[v].parent == -1) {
- return v;
- }
- return dsuf[v].parent = Find(dsuf[v].parent);
- }
- void Union(int root_of_from, int root_of_to) {
- // there will be three cases in merging the subsets:
- // case 1 - if the rank of the absolute root (parent) of 'from' is greater than the absolute root (parent)
- // of 'to', then set the absolute root (parent) of 'to' to the absolute root (parent) of 'from'
- // case 2 - if the rank of the absolute root (parent) of 'from' is less than the absolute root (parent)
- // of 'to', then set the absolute root (parent) of 'from' tot the absolute root (parent) of 'to'
- // cae 3 - if the ranks of the absolute roots of the two vertices given ('from' and 'to') are the
- // same, then arbitrarily choose one among them to be the absolute root (parent ) of the other vertex
- // and do not forget to increase the rank of the newly chosen absolute root (parent)
- if (dsuf[root_of_from].rank > dsuf[root_of_to].rank) {
- dsuf[root_of_to].parent = root_of_from;
- } else if (dsuf[root_of_from].rank < dsuf[root_of_to].rank) {
- dsuf[root_of_from].parent = root_of_to;
- } else {
- dsuf[root_of_from].parent = root_of_to;
- dsuf[root_of_to].rank++;
- }
- }
- bool IsCyclic(vector<pair<int, int>>& edge_list) {
- for (auto& p : edge_list) {
- // find the absolute roots (parents) of the two vertices and check if it forms a cycle,
- // then merge the vertices in one subset by making their absolute root the same
- int root_of_from = Find(p.first);
- int root_of_to = Find(p.second);
- if (root_of_from == root_of_to) {
- return true;
- }
- Union(root_of_from, root_of_to);
- }
- return false;
- }
- int main() {
- // input number of edges and vertices
- int E, V;
- cin >> E >> V;
- // mark all vertices as separate subsets with only one (1) element
- // create an adjacency list (using nodes) and set their parent and rank to -1 and 0 respectively
- dsuf.resize(V);
- for (int i = 0; i < V; i++){
- dsuf[i].parent = -1;
- dsuf[i].rank = 0;
- }
- // form the edges of every two vertices
- vector<pair<int, int>> edge_list;
- for (int i = 0; i < E; i++) {
- int from, to;
- cin >> from >> to;
- edge_list.push_back(make_pair(from, to));
- }
- // check if the tree structure forms a cycle
- if (IsCyclic(edge_list)) {
- cout << "TRUE";
- } else {
- cout << "FALSE";
- }
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement