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[0])))

typedef long double LD;

vector<int> v[1005],sv[1005];
vector<int> topo;
int used[1005],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!!!!
**********************************/