09.Detect_cycle_DFS.md

Detect Cycle - DFS

Thought Process: If any of the adjacent node other than parent is already visited then there is a cycle

Driver code would be same, We'll call dfs for all the components, it is just that the dfs would be implemmented in a little different way.

Here in this graph, we'll call DFS for each node one by one, in the order 2->3->6->7->8 but now when DFS will be called for 8, then it will call it's adjacent node, i.e, 5. Then we'll find out that 5 is already visited, so it can only be visited if we are trying to access it the second time, that does mean there is a cycle. Had it not been a cycle then we would have never got a node which is already visited.

• But there is a twist here, whenever you'll traverse you'll always have one adjacent node which would be always visited i.e, the previous node, so we have to see that apart from the previous node if there is any node which is already visited then only we'll claim that there is a cycle, so we'll always carry parent.

• while calling it for the first time, pass the parent as -1, as parent of 1st node is none.

• Now steps would be:

  • Call dfs for first node and pass parent as -1
  • Mark it as visited
  • Check if any of the adjacent node is visited apart from the parent then there is a cycle so return true.
  • If not visited then call dfs for its adjacent nodes.
  • so until last if no one return true then return false, i.e, there isn't any cycle.
  • The moment anyone return true, brak from there as we don't need to find out the number of cycles, we jsut need to find out whether there is a cycle or not, so no need to traverse further.
  • Similarly for the components, if any of the component returns true, then break from there, no need to check for other components.

Time Complexity and Space complexity:

• Time complexity would be same as DFS i,e O(N+E) N is time taken for visiting N nodes, and E is for traveling through adjacent nodes overall.
• Space Complexity would be O(N+E) + O(N) + O(N) for adjacency list, visited array and auxilliary space.

0 Based Indexing

#include<bits/stdc++.h>
using namespace std;

bool checkCycleDFS(int node, int par, vector<int> &vis, vector<int> adj[]){
    vis[node] = 1;
    for(auto it : adj[node]){
        if(!vis[it]){
            if(checkCycleDFS(it, node, vis, adj)) return true;
        }
        else if(it != par) return true;
    }
    return false;
}

bool isCycle(int v, vector<int> adj[]){
    vector<int> vis(v, 0);
    
    
    for(int i=0; i<v; i++){
        if(!vis[i]){
            if(checkCycleDFS(i, -1, vis, adj)) return true;
        }
    }
    return false;
}

int main(){
    int n, m;
    cin>>n>>m;
    
    vector<int> adj[n];
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if(isCycle(n, adj)) cout<<"Yes";
    else cout<<"No";
    return 0;
}

1 Based Indexing

#include<bits/stdc++.h>
using namespace std;

bool checkCycleDFS(int node, int par, vector<int> &vis, vector<int> adj[]){
    vis[node] = 1;
    for(auto it : adj[node]){
        if(!vis[it]){
            if(checkCycleDFS(it, node, vis, adj)) return true;
        }
        else if(it != par) return true;
    }
    return false;
}

bool isCycle(int v, vector<int> adj[]){
    vector<int> vis(v+1, 0);
    
    
    for(int i=1; i<=v; i++){
        if(!vis[i]){
            if(checkCycleDFS(i, -1, vis, adj)) return true;
        }
    }
    return false;
}

int main(){
    int n, m;
    cin>>n>>m;
    
    vector<int> adj[n+1];
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if(isCycle(n, adj)) cout<<"Yes";
    else cout<<"No";
    return 0;
}