CODEWITHSUNDEEP
algorithmgraph
user3243499
user3243499

Reputation: 3151

How to check if a undirected cycle is formed given a set of edges and what is its complexity?

I have been given only a set of edges and asked if there is a cycle in the graph (graph may not be connected). I know it can be easily solved using a simple DFS. But I would like to know if there is any other method with reduced complexity as I may receive multiple such queries to check for cycles and running dfs every time would give O(nq) complexity, n number of edges and q number of queries.

Upvotes: 1

Views: 95

Answers (1)

Anonta
Anonta

Reputation: 2540

You can use Disjoint sets, It can find all cycles in O(E) (E is number of edges)

What it does:

  1. Keeps track of which nodes are connected, directly or indirectly (Meaning the two nodes are in the same set).

  2. Put two nodes in the same set. (Meaning they are connected). Actually, it does a union of the two sets these nodes are from.

Disjoint set does both of these operations in O(1). Here's how I implement Disjoint set with path compression:

#include <iostream>
#include <cstdio>

using namespace std;

// This array is used to represent a backward tree (Forest actually)
// all nodes part of a tree are in the same set
int disjointset[1000];

// at first all nodes are separated
// that is they are part of a 1 element set
void initialize(int n){
    for(int i= 0; i<=n; i++){
        disjointset[i]= i;
    }
}

// get the root parent of node a in disjoint tree structure
int getParent(int a){
    if(disjointset[a] == a)
        return a;

    // we do this assignment to shorten the path from this node to it's top ancestor in tree
    // this is called path compression
    disjointset[a] = getParent(disjointset[a]);

    return disjointset[a];
}

// check if two nodes are directly/indirectly connected
bool connected(int a, int b){
    return getParent(a) == getParent(b);
}

// join two nodes a and b, after this they will be connected
void join(int a, int b){
    disjointset[getParent(a)] = getParent(b);
}

int main(){
    //freopen("F:/input.txt", "r", stdin);

    // n nodes, e edges
    int n, e, u, v;

    cin>>n>>e;   // e number of edges

    //initialize the backward tree of disjoint set
    initialize(n);

    for(int i= 0; i<e; i++){
        cin>>u>>v;

        if(connected(u, v)){
            cout<< "Cycle found"<<endl;
        }

        join(u,v);
    }

}


/*

//sample input
//6 nodes 6 edges
6 6
1 2
2 3
1 3
3 4
3 5
4 6

*/

Note: Inserting the same edge multiple times will be counted as a cycle.

Upvotes: 2

Related Questions