notebook/code/SCC.cc

struct edge { int e, nxt; };
int V, E;
edge e[MAXE], er[MAXE];
int sp[MAXV], spr[MAXV];
int group_cnt, group_num[MAXV];
bool v[MAXV];
int stk[MAXV];
void fill_forward(int x) {
  int i;
  v[x]=true;
  for(i = sp[x]; i; i = e[i].nxt)
    if(!v[e[i].e])
      fill_forward(e[i].e);
  stk[++stk[0]] = x;
}
void fill_backward(int x) {
  int i;
  v[x]=false;
  group_num[x] = group_cnt;
  for(i = spr[x]; i; i = er[i].nxt)
    if(v[er[i].e])
      fill_backward(er[i].e);
}
void add_edge(int v1, int v2) { //add edge v1->v2
  e [++E].e = v2; e [E].nxt = sp [v1]; sp [v1] = E;
  er[  E].e = v1; er[E].nxt = spr[v2]; spr[v2] = E;
}
void SCC() {
  int i;
  stk[0] = 0;
  memset(v, false, sizeof(v));
  for(i = 1; i <= V; i++)
    if(!v[i])
      fill_forward(i);
  group_cnt = 0;
  for(i = stk[0]; i >= 1; i--)
    if(v[stk[i]]) {
      group_cnt++;
      fill_backward(stk[i]);
    }
}