SCC problem with kosaraju’s algorithm

Problem extracted from coursera.org:

Download the text file here. Zipped version here. (Right click and save link as)

The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Every row indicates an edge, the vertex label in first column is the tail and the vertex label in second column is the head (recall the graph is directed, and the edges are directed from the first column vertex to the second column vertex). So for example, the 11th row looks liks : “2 47646”. This just means that the vertex with label 2 has an outgoing edge to the vertex with label 47646

Your task is to code up the algorithm from the video lectures for computing strongly connected components (SCCs), and to run this algorithm on the given graph.

Output Format: You should output the sizes of the 5 largest SCCs in the given graph, in decreasing order of sizes, separated by commas (avoid any spaces). So if your algorithm computes the sizes of the five largest SCCs to be 500, 400, 300, 200 and 100, then your answer should be “500,400,300,200,100”. If your algorithm finds less than 5 SCCs, then write 0 for the remaining terms. Thus, if your algorithm computes only 3 SCCs whose sizes are 400, 300, and 100, then your answer should be “400,300,100,0,0”.

The idea of Kosaraju’s algorithm is like this:
1. Compute the finishing time of all the vertices by doing a DFS on the reversed graph;
2. Replace the vertex index with its finishing time to get a new graph, DFS the new graph to compute each vertex’s leader vertex( in a strongly connected component(SCC) if exists any);
3. Do statistical job on the leader vertices’ index. If multiple vertices have same leader vertex, they are in the same SCC.

Here is a quick Python implementation on the problem without any optimization work:

import sys
sys.setrecursionlimit(300000)
source='SCC.txt'
N=875714
def getG():
    G={}
    Grev={}
    for i in range(1,N+1):
        G[i]=[]
        Grev[i]=[]
    fin=open(source)
    for line in fin:
        v1=int(line.split()[0])
        v2=int(line.split()[1])
        G[v1].append(v2)
        Grev[v2].append(v1)
    fin.close()
    return G, Grev

#globals
visited={}
finish={}
leader={}

def init():
    for i in range(1,N+1):
        visited[i]=0
        finish[i]=0
        leader[i]=0

def dfs(G, i):
    global t
    visited[i]=1
    leader[i]=s
    for j in G[i]:
        if(visited[j]==0): dfs(G,j)
    t=t+1
    finish[i]=t

def dfs_loop(G):
    global t
    global s
    t=0 #number of nodes processed so far
    s=0 #current source vertex
    i=N
    while(i>0):
        if(visited[i]==0):
            s=i
            dfs(G,i)
        i=i-1

if __name__ == "__main__":
    init()
    g, grev=getG()
    dfs_loop(grev) #THE FIRST LOOP ON REVERSE GRAPH

    # construct new graph
    newGraph={}
    for i in range(1,N+1):
        temp=[]
        for x in g[i]: temp.append(finish[x])
        newGraph[finish[i]]=temp

    init()    
    dfs_loop(newGraph) #THE SECOND LOOP 

    # statistics
    lst= sorted(leader.values())
    stat=[]
    pre=0
    for i in range(0,N-1):
        if lst[i]!=lst[i+1]:
            stat.append(i+1-pre)
            pre=i+1
    stat.append(N-pre)
    L= sorted(stat)
    L.reverse()
    print(L[0:5])

Here is the C/C++ code directly translated from the Python. (Unlike the Python code above, I did the statistical job externally.）

#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#define N 875714
using namespace std;

struct node{
    bool visited;
    int leader;
    int finish;
    vector<int> linkedVertices;
    vector<int> rLinkedVertices;
};

struct node G[N+1];
struct node newG[N+1];

int t=0;
int s=0;
void dfs(node G[], int i, bool reverse){
    G[i].visited=true;
    G[i].leader=s;
    vector<int> next;
    if (reverse) next= G[i].rLinkedVertices;
    else next= G[i].linkedVertices;
    for(int j=0; j<next.size(); j++){
        if(!G[next[j]].visited) {
            dfs(G, next[j], reverse);
        }
    }
    t++;
    G[i].finish=t;    
}

void dfs_loop(node G[], bool reverse){
    t=0;
    s=0;
    for(int i=N;i>0;--i){
        if (!G[i].visited){
            s=i;
            dfs(G,i,reverse);
        }
    }
}

int main(){
    for(int i=1;i<=N;++i){
        G[i].visited=false;
    }

    FILE* fp=freopen("SCC.txt","r",stdin);
    int head, tail;
    while (scanf("%d %d", &head, &tail) > 0) {
              G[head].linkedVertices.push_back(tail);
              G[tail].rLinkedVertices.push_back(head);
    }
    fclose(fp);

    dfs_loop(G, true);//FIRST LOOP

    for(int i=1;i<=N;++i){
        newG[i].visited=false;
        newG[i].finish=0;
        newG[i].leader=0;
        vector<int> temp;
        for(int j=0; j< G[i].linkedVertices.size(); j++){
            temp.push_back(G[G[i].linkedVertices[j]].finish);
        }
        newG[G[i].finish].linkedVertices=temp;
    }

    dfs_loop(newG,false);//SECOND LOOP

    ofstream ofs("stat.txt", ofstream::out);    
    for (int k=1;k<=N;k++) ofs<< newG[k].leader<<endl;
    ofs.close();
    return 0;
}