Finding the number of strongly connected components

Question

I have wrote this code for finding the number of SCC (strongly connected components):

#include <iostream>
#include <vector>
using namespace std;
int n , m;
vector<vector<int>>G(101) , GT(101);

void read()
{
    //n = number of nodes , m = number of edges.
    cin>>n>>m;

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

void DFS_G(int node , vector<int>&V)
{
    V[node] = 1;

    for (int x : G[node])
    {
        if (!V[x])
            DFS_G(x , V);
    }
}

void DFS_GT(int node , vector<int>&V)
{
    V[node] = 1;

    for (int x : GT[node])
    {
        if (!V[x])
            DFS_GT(x , V);
    }
}

int main()
{
    //G-graph
    //GT-reversed graph
    int SCC = 0;
    read();
    vector<int>component(101 , 0);
    vector<int>reachedG(101) , reachedGT(101);//will keep nodes reached from x in G and in GT

    for (int i = 1 ; i <= n ; i++)
    {
        if (!component[i])
        {

        component[i] = 1;

        for(int j = 1 ; j <= n ; j++)
        {
            reachedG[j] = reachedGT[j] = 0;
        }

        DFS_G(i , reachedG);
        DFS_GT(i , reachedGT);

        for (int j = 1 ; j <= n ; j++)
        {
            if (reachedG[j] == 1 && reachedGT[j] == 1)
            {
                component[j] = 1;
            }
        }
        SCC++;

        }
    }
    cout<<SCC;
    return 0;
}

Let's say you are at node X.First we DFS from X , and find the nodes that we can reach from it.We mark them as reached in our reachedG vector.As you may know , by reversing a graph and then DFS from x , the nodes you will encounter are actually the nodes that can reach X.I keep them in reachedGT.So the intersection between these two vectors will actually be the SCC our node X is in.However , as I read on the internet, this isn't the best implementation of Kosaraju's algorithm.The more efficient one is this one from https://www.geeksforgeeks.org/strongly-connected-components/.

The steps are the following:

Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.
Reverse directions of all arcs to obtain the transpose graph.
One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1 (One by one popped from stack).

I've spent quite some hours reading about it and I still don't understand the logic behind the stack with finishing times of our nodes.However , I think this approach is really similar to mine and that I'm missing something.I'd be happy if you helped me!

David Eisenstat David Eisenstat · Accepted Answer · 2021-03-20T22:50:00

Let v be the last node to be finished. Every node that can reach v in the original graph (hence that v can reach in the transpose) is in v's strong component. Why? Suppose to the contrary that x is a node that can reach v, but v can't reach x. When we start x, the node v cannot be on the stack at the time because that would imply a path to x. We can't finish x until we've at least started every node that x can reach, so if v starts before x, it's already finished (because not on the stack), and if v starts after x, it finishes before x (because it's higher on the stack than x). Contradiction. This argument extends to a correctness proof.

Finding the number of strongly connected components

1 Answers