﻿ Tips And Tutorial - Presented by Oneous!

Strongly Connected Component Algorithm (SCC)
Last Update: 6 March, 2009

Problem: The strongly connected components (SCC) of a directed graph G are its maximal strongly connected subgraphs. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of G. A directed graph is acyclic if and only if it has no (nontrivial) strongly connected subgraphs (because a cycle is strongly connected, and every strongly connected graph contains at least one cycle).
Given a directed graph, find how many strongly connected component is in the graph.

My Code:

``````// C++ Code : Strongly Connected Component Algorithm (SCC
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define INF  1073741822
#define MAX(a,b)  ((a>b)?a:b)
#define MIN(a,b)  ((a<b)?a:b)
#define CLEAR(A,N)  (memset(A,0,(N)*sizeof(A)))

typedef long double LD;

vector<int> v,sv;
vector<int> topo;
int used,M,N;

void DFS(int s){
int i;
used[s]=1;
for(i=0;i<v[s].size();i++){
if(used[v[s][i]]==0)
DFS(v[s][i]);
}
topo.push_back(s);
}

void anotherDFS(int s){
int i;
used[s]=1;
for(i=0;i<sv[s].size();i++){
if(used[sv[s][i]]==0)
anotherDFS(sv[s][i]);
}
}

int findSCC(int N){
int res,i;
CLEAR(used,N+1);
for(i=1;i<=N;i++){
if(used[i]==0)
DFS(i);
}
CLEAR(used,N+1);
res=0;
for(i=topo.size()-1;i>=0;i--){
if(used[topo[i]]==0){
anotherDFS(topo[i]);
res++;
}
}
return res;
}

int main() {
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)

int test,t,a,b,i,res;

scanf("%d",&test);
for(t=1;t<=test;t++){
// N is the number if Node, M is the number of Edg
scanf("%d %d",&N,&M);
for(i=0;i<M;i++){
scanf("%d %d",&a,&b);
v[a].push_back(b);
sv[b].push_back(a);
}
res=findSCC(N);

printf("%d\n",res);

//CLEAR all vector
for(i=1;i<=N;i++){
v[i].clear();
sv[i].clear();
}
topo.clear();

}

// End of main function.......
return 0;
}

/***  Programmed by:
###########################
##   ~  ORONNO  ~		 ##
## 	CSEDU 12th Batch.	 ##
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/``````