Topological Sort and Strongly Connected Components

Topological Sorting and finding Strongly Connected Components are classical problems on Directed Graphs. Here we will see how we can do Topological Sorting by using DFS and Find Strongly Connected Components using Kosaraju's Algorithm.
Topological Sorting Algorithm:
1) Start with any node and perform a DFS on the graph marking visited nodes.
2) If a node has no unvisited neighbours, add it to the front of a linked list.
3) Repeat till all nodes are visited.
Instead of using a linked list we just push_back normally into a C++ vector. The final vector will give reverse of the topologically sorted order.
Strongly Connected Components Algorithm:
1) Do Topological Sort.
2) Find transpose of the graph: It is defined as - if (u,v) is an edge in original graph, (v,u) is an edge in the transpose
3) Do a DFS on the transpose of the graph in topologically sorted order.
4) Each vertex of the so formed depth-first forest is a separate strongly connected component. Mark them, count the number of them etc.

vector<int> a[1005],atr[1005],topo;
bool seen[1005];
int comp[1005],indeg[1005];
int n,c;

void dfs(int node) // Topological Sorting
{
 seen[node]=true;
 REP(i,0,a[node].size())
 {
  if(seen[a[node][i]]==false)
   dfs(a[node][i]);
 }
 topo.push_back(node);
}

void dfst(int node)
{
 seen[node]=true;
 comp[node]=c;
 REP(i,0,atr[node].size())
 {
  if(seen[atr[node][i]]==false)
   dfst(atr[node][i]);
 }
}

int SCC()
{
 int result=0;
 memset(seen, false, sizeof seen);
 REP(i,1,n+1)
 {
  if(seen[i]==false)
   dfs(i);
 }
 memset(seen,false,sizeof seen);
 memset(comp,0,sizeof comp);
 c=0;
 for(int i=topo.size()-1;i>=0;i--)
 {
  if(seen[topo[i]]==false)
   {dfst(topo[i]);c++;}
 }
 return c;
}

Practice Problem:
CAPCITY