Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> parent;
- int Find(int v) {
- // traverse the tree structure in order to find the absolute root of a vertex
- if (parent[v] == -1) {
- return v;
- }
- return Find(parent[v]);
- }
- void Union(int root_of_from, int root_of_to) {
- // find the absolute roots of the two vertices again and change the absolute root
- // of one vertex to the absolute root of the other vertex so they have the same absolute root
- root_of_from = Find(root_of_from);
- root_of_to = Find(root_of_to);
- parent[root_of_from] = root_of_to;
- }
- bool IsCyclic(vector<pair<int, int>>& edge_list) {
- for (auto& p : edge_list) {
- // find the absolute roots 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
- // and create the adjacency list based on the number of edges and vertices
- parent.resize(V, -1);
- 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 graph forms a cycle
- if (IsCyclic(edge_list)) {
- cout << "TRUE";
- } else {
- cout << "FALSE";
- }
- cout << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment