Day 41 | Cycle Detection in Graphs | C++

Detecting the cycle and printing it is a very important skill you will need. It might either be to actually find a cycle as an answer or as a step to make an answer for a bigger problem.

Let's get started with it without wasting any time.

What is a cycle [Basics are important]?

If there exists a path in the graph including at least 2 vertices, where you can reach the vector you started from, at the end of the path.

For example, in the graph below -

Here these paths form a cycle (although the same)

1. 2 - 3 - 4 - 2

2. 3 - 4 - 2 - 3

3. 4 - 2 - 3 - 4

How do we detect a cycle?

Undirected Graph

To detect a cycle in an undirected graph is quite simple.

1. Run DFS

2. If any adjacent node (except the parent) is already visited, then there is a cycle.

Something like this

Concept -

Since DFS runs in a single component, this means that all the nodes it visits in one run are connected in one way or another.

Now think this

1. u was visited before v

2. u is not a parent of v

3. Thus there is a path to reach v from u, without using edge u--v

4. Thus if we add this edge now, we will get a cycle.

You can simply code it like this

bool dfs(int u, int parent){
    vis[u] = 1;
    for(int v : g[u]){
        if(v == parent)continue;
        if(vis[v]){
           return true;
        }
        if(dfs(v,u))return true;
    }
    return false;
}

Directed Graph

The first problem is why the algorithm we use in the undirected graph does not work here

See this then

Now, the above algorithm says there is a cycle there, but do you see a cycle there?

Notice that just because we visited a node before doesn't mean we can reach to current node from a visited node. For that, there is a condition. But before telling the condition let's understand about recursion of DFS in the above diagram

1. DFS(1)

2. DFS(2) with Stack = (DFS(1))

3. DFS(3) with Stack = (DFS(1), DFS(2))

4. None with Stack = (DFS(1), DFS(2), DFS(3))

5. Pop DFS(3) with Stack = (DFS(1), DFS(2))

6. Pop DFS(2) with Stack = (DFS(1))

7. Pop DFS(1) with Stack = Empty

8. DFS(5) with Stack = Empty

9. DFS(4) with Stack = (DFS(5))

10. None with Stack = (DFS(4), DFS(5))

11. Pop DFS(4) with Stack = (DFS(5))

12. Pop DFS(5) with Stack = Empty

Yes, you are right. Nodes in the stack are all the nodes from which we can reach the current node. Thus for the edge to the visited node to be a cycle, the visited node should be in the stack.

Like this

You can detect this cycle like this -

bool dfs(int u){
    vis[u] = 1; // 1 means in stack
    for(int v : g[u]){
        if(vis[v] == 1){
           return true;
        }
        if(vis[v] == 2)continue;
        if(dfs(v))return true;
    }
    vis[u] = 2; // Exiting Stack
    return false;
}

How to print cycle? (Easier to understand way)

We know the cycle between v-u after DFS. Now you just need a path from v to u which we have already discussed here - Actually getting the shortest path

You can implement it like this First DFS

bool dfs(int u, int parent){
    vis[u] = 1;
    for(int v : g[u]){
        if(v == parent)continue;
        if(vis[v]){
            cycle_source = v;
            cycle_end = u;
            return true;
        }
        if(dfs(v,u))return true;
    }
    return false;
}

Using cycle_source and cycle_end to find parents

void dfs_mark_parents(int u, int parent){   
    vis[u] = 1;
    par[u] = parent;
    for(int v : g[u]){
        if(vis[v])continue;
        dfs_mark_parents(v,u);
    }
}

Using paths to find Cycle

vector<int> cycle;
cycle.push_back(cycle_source);
while(cycle_end != -1){
    cycle.push_back(cycle_end);
    cycle_end = par[cycle_end];
}

Let's solve Round Trip

This is directly the implementation for the undirected graph cycle finding

Click to see the Solution

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

const int N = 1e5 + 10;
int vis[N], par[N];
vector<int> g[N];
int cycle_source, cycle_end;

bool dfs(int u, int parent){
    vis[u] = 1;
    for(int v : g[u]){
        if(v == parent)continue;
        if(vis[v]){
            cycle_source = v;
            cycle_end = u;
            return true;
        }
        if(dfs(v,u))return true;
    }
    return false;
}

void dfs_mark_parents(int u, int parent){   
    vis[u] = 1;
    par[u] = parent;
    for(int v : g[u]){
        if(vis[v])continue;
        dfs_mark_parents(v,u);
    }
}

int main(){
    int m,n;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bool found_cycle; 
    for(int i = 1; i <= n ; i++){
        if(vis[i])continue;
        found_cycle = dfs(i,-1);
        if(found_cycle)
            break;
           
    }
    if(!found_cycle){
        return cout << "IMPOSSIBLE\n", 0;
    }
    memset(vis,0,sizeof(vis));
    dfs_mark_parents(cycle_source,-1);
    vector<int> cycle;
    cycle.push_back(cycle_source);
    while(cycle_end != -1){
        cycle.push_back(cycle_end);
        cycle_end = par[cycle_end];
    }
    cout << cycle.size() << "\n";
    for(int i: cycle)cout << i << " ";
}

Let's solve Round Trip - II

This is directly the implementation for the directed graph cycle finding

Click to see the Solution

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

const int N = 1e5 + 10;
int vis[N], par[N];
vector<int> g[N];
int cycle_source, cycle_end;

bool dfs(int u){
    vis[u] = 1;
    for(int v : g[u]){
        if(vis[v] == 1){
            cycle_source = v;
            cycle_end = u;
            return true;
        }
        if(vis[v] == 2)continue;
        if(dfs(v))return true;
    }
    vis[u] = 2;
    return false;
}

void dfs_mark_parents(int u, int parent){   
    vis[u] = 1;
    par[u] = parent;
    for(int v : g[u]){
        if(vis[v])continue;
        dfs_mark_parents(v,u);
    }
}

int main(){
    int m,n;
    scanf("%d %d",&n, &m);
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a, &b);
        g[a].push_back(b);
    }

    bool found_cycle; 
    for(int i = 1; i <= n ; i++){
        if(vis[i])continue;
        found_cycle = dfs(i);
        if(found_cycle)
            break;
           
    }
    if(!found_cycle){
        return cout << "IMPOSSIBLE\n", 0;
    }
    memset(vis,0,sizeof(vis));
    dfs_mark_parents(cycle_source,-1);
    vector<int> cycle;
    while(cycle_end != -1){
        cycle.push_back(cycle_end);
        cycle_end = par[cycle_end];
    }
    reverse(cycle.begin(),cycle.end());
    cycle.push_back(cycle_source);
    printf("%d\n",cycle.size());
    for(int i: cycle)printf("%d ",i);
}

Printing Cycle [Easy to implement method]

Notice this -

1. We are running DFS

2. We have a visited node v already.

3. Now v must be the ancestor of u in the current stack, Reason - For v to go out of the stack, all the neighbors of v must have been visited/ u is a neighbor of v because there is an edge u-v Since v is not a parent of u, it must be in the stack of u

Therefore, if you are storing parents of all nodes. v is an ancestor of u in DFS. This means that if we just keep finding paths from u using par[], we will find v eventually.

Solving Cycle in a graph

Since I stated that v will always be an ancestor of u, then you simply find the cycle length using Length_from_starting_point[v] - Length_from_starting_point[v] + 1

That's right, the rest is the same.

Examples

Input 0

3 3 2
1 2
2 3
3 1

Output 0

3
1 2 3 

Input 1

4 6 3
4 3
1 2
1 3
1 4
2 3
2 4

Output 1

4
3 4 1 2 

Click here to see the solution

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

int m,n,k;
const int N = 1e5 + 10;
int vis[N], par[N], len[N];
vector<int> g[N];
int cycle_source, cycle_end;

bool dfs(int u, int parent, int length){
    vis[u] = 1;
    par[u] = parent;
    len[u] = length;
    for(int v : g[u]){
        if(v == parent)continue;
        if(vis[v] && len[u] - len[v] + 1 > k){
            cycle_source = v;
            cycle_end = u;
            return true;
        }
        if(vis[v] == 0){
            if(dfs(v,u,length+1))return true;
        }
    }
    return false;
}

int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bool found_cycle; 
    for(int i = 1; i <= n ; i++){
        if(vis[i])continue;
        found_cycle = dfs(i,-1,0);
        if(found_cycle)
            break;    
    }
    vector<int> cycle;
    while(cycle_end != cycle_source){
        cycle.push_back(cycle_end);
        cycle_end = par[cycle_end];
    }
    cycle.push_back(cycle_source);
    cout << cycle.size() << "\n";
    for(int i: cycle)cout << i << " ";
}