The following is a C++ implementation demonstrating Kosaraju's Two-Pass Algorithm to find strongly connected components within a directed graph. An input file containing vertex edges is used to build a directed graph (and the reverse graph).

main.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>

namespace std {   };
using namespace std;

void build_graphs_from_stream(istream& is, vector<vector<size_t> >& graph, vector<vector<size_t> >& reverse_graph)
{
   size_t i = 0, j = 0;

   is >> i;
   graph.resize(i);
   reverse_graph.resize(i);

   while (is >> i >> j)
   {
      --i; --j;
      if (i != j)
      {
         graph[i].push_back(j);
         reverse_graph[j].push_back(i);
      }
   }

   return;
}

void calculate_leaders_using_DFS(vector<vector<size_t> >& graph, vector<bool>& explored, size_t i, vector<size_t>& leader, size_t s)
{
   explored[i] = true;

   leader[i] = s;

   for (size_t j = 0; j < graph[i].size(); ++j)
   {
      if (explored[graph[i][j]] == false)
      {
         calculate_leaders_using_DFS(graph, explored, graph[i][j], leader, s);
      }
   }

   return;
}

void calculate_leaders_using_DFS_loop(vector<size_t>& finish_time, vector<vector<size_t> >& graph, vector<size_t>& leader)
{
   size_t s = 0;
   vector<bool> explored(graph.size(), false);

   for (size_t i = finish_time.size(); i > 0; --i)
   {
      size_t j = i - 1;
      if (explored[finish_time[j]] == false)
      {
         s = j;
         calculate_leaders_using_DFS(graph, explored, finish_time[j], leader, s);
      }
   }

   return;
}

void calculate_finish_times_using_DFS(vector<vector<size_t> >& graph, vector<bool>& explored, size_t i, vector<size_t>& finish_time, size_t& t)
{
   explored[i] = true;

   for (size_t j = 0; j < graph[i].size(); ++j)
   {
      if (explored[graph[i][j]] == false)
      {
         calculate_finish_times_using_DFS(graph, explored, graph[i][j], finish_time, t);
      }
   }

   finish_time[t] = i;
   ++t;

   return;
}

void calculate_finish_times_using_DFS_loop(vector<vector<size_t> >& graph, vector<size_t>& finish_time)
{
   size_t t = 0;
   vector<bool> explored(graph.size(), false);

   for (size_t i = 0; i < graph.size(); ++i)
   {
      if (explored[i] == false)
      {
         calculate_finish_times_using_DFS(graph, explored, i, finish_time, t);
      }
   }

   assert(t == graph.size());

   return;
}

size_t count_strongly_connected_components(map<size_t, size_t>& scc, vector<vector<size_t> >& graph, vector<vector<size_t> >& reverse_graph)
{
   vector<size_t> finish_time(graph.size(), 0);
   calculate_finish_times_using_DFS_loop(reverse_graph, finish_time);

   vector<size_t> leader(graph.size(), 0);
   calculate_leaders_using_DFS_loop(finish_time, graph, leader);

   for (size_t i = 0; i < leader.size(); ++i)
   {
      scc[leader[i]]++;
   }

   return scc.size();
}

int main(int argc, char* argv[])
{
   vector<vector<size_t> > graph, reverse_graph;

   if (argc > 1)
   {
      ifstream ifs;
               ifs.open(argv[1]);

      build_graphs_from_stream(ifs, graph, reverse_graph);

      ifs.close();
   }

   assert(graph.size() == reverse_graph.size());
   assert(graph.size() == 9);

   map<size_t, size_t> scc;
   count_strongly_connected_components(scc, graph, reverse_graph);

   cout << "Number of Strongly Connected Components: " << scc.size() << endl;

   size_t sum = 0;
   for (map<size_t, size_t>::const_iterator it = scc.begin(); it != scc.end(); ++it)
   {
      sum += it->second;
      cout << it->second << ", ";
   }

   assert(sum == graph.size());

   cout << endl;

   cin.get();

   return 0;
}

small_adj_list.txt

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