C++ :: Strongly Connected Components Algorithm (SCC)

Many algorithms that work with directed graphs begin with such a decomposition. After decomposing the graph into strongly connected components, such algorithms run separately on each one and then combine the solutions according to the structure of connections among components.

ALGORITHM

STRONGLY-CONNECTED-COMPONENTS(G)
    call DFS(G) to compute finishing times u.f for each vertex u
    compute GT
    call DFS(GT), but in the main loop of DFS, consider the verteces in order of decreasing u.f (as computed in line 2)
    output the vertices of each tree in the depth-first forest formed in line 4 as a separate strongly connected component

C++ Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], f[MAX], t, vertex, edge, forest;
int NIL = numeric_limits<int>::min();

vector<int> sccVertex;
list<int> orderedList;
list<int>::iterator it;

void STRONGLY_CONNECTED_COMPONENTS(vector<int>[],vector<int>[]);
void DFS(vector<int>[]);
void DFS_VISIT(vector<int>[],int);
void DFS_GT(vector<int>[]);
void DFS_VISIT_GT(vector<int>[],int);

int main(void)
{
    //freopen("scc.txt", "r", stdin);
    vector<int> G[MAX];
    vector<int> GT[MAX];
    G[MAX].clear();
    int u, v;
    cin >> vertex >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        G[u].push_back(v);
        GT[v].push_back(u);
    }
    STRONGLY_CONNECTED_COMPONENTS(G,GT);
    return 0;
}

void STRONGLY_CONNECTED_COMPONENTS(vector<int> G[], vector<int> GT[]) {
    DFS(G);
    DFS_GT(GT);
}

void DFS(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0;
    for(int u=1; u<=vertex; u++) {
        if(color[u] == WHITE) {
            DFS_VISIT(G,u);
        }
    }
}

void DFS_VISIT(vector<int> G[], int u) {
    t = t + 1;
    d[u] = t;
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++) {
        if(color[G[u][v]] == WHITE) {
            p[G[u][v]] = u;
            DFS_VISIT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
    orderedList.push_front(u);
}

void DFS_GT(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0, forest = 0;
    int flag = orderedList.size()-1;
    for(it=orderedList.begin(); it != orderedList.end(); ++it) {
        if(color[*it] == WHITE) {
            DFS_VISIT_GT(G,*it);
            forest++;
            sort(sccVertex.rbegin(), sccVertex.rend());
            while( !sccVertex.empty()) {
                cout << sccVertex.back();
                sccVertex.pop_back();
            }
            if(flag) cout << " -> ";
        }
        --flag;
    }
    cout << endl;
}

void DFS_VISIT_GT(vector<int> G[], int u) {
    t = t + 1;
    d[u] = t;
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++) {
        if(color[G[u][v]] == WHITE) {
            p[G[u][v]] = u;
            DFS_VISIT_GT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
    sccVertex.push_back(u);
}

Sample Input

8 14
1 2
2 3
2 5
2 6
3 4
3 7
4 3
4 8
5 1
5 6
6 7
7 6
7 8
8 8

Sample Output

125 -> 34 -> 67 -> 8

SCC Related UVa Problems

• 125 - Numbering Paths
• 247 - Calling Circles
• 10319 - Manhattan
• 10731 - Test
• 11324 – The Largest Clique
• 11390 - The Sultan's Feast
• 11504 – Dominos
• 11709 – Trust Groups
• 11770 – Lighting Away

Refference: Introduction to Algorithms - Thomas H. Cormen