## Sunday, May 24, 2015

### SPOJ BOTTOM Solution : Strongly Connected Components : Kosaraju's Algorithm

Problem : http://www.spoj.com/problems/BOTTOM/

Source: C++ AC (0.02s):

```#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int V, E;
vector<vector<int> > G;
vector<vector<int> > GD;
vector<vector<int> > res;

vector<int> sortOrder;

bool *marked;
int *reg;
int groupNo;

void dfs(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<G[vertex].size();++i) dfs(G[vertex][i]);
sortOrder.push_back(vertex);
}

void dfs2(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<GD[vertex].size();++i)dfs2(GD[vertex][i]);
res[groupNo].push_back(vertex);
reg[vertex] = groupNo;
}

int main(){
while(true){
scanf(" %d", &V);
if(V==0)break;
scanf(" %d", &E);

marked = new bool[V];
for(int i=0;i<V;++i)marked[i] = false;
reg = new int[V];
for(int i=0;i<V;++i)reg[i] = -1;

sortOrder.clear();
G.clear();
GD.clear();
res.clear();
groupNo = -1;

for(int i=0;i<V;++i){
vector<int> t,tt,ttt;
res.push_back(t);
G.push_back(tt);
GD.push_back(ttt);
}

if(E!=0){
for(int j=0;j<E;++j){
int from, to;
scanf(" %d %d", &from, &to);
from--;
to--;
G[from].push_back(to);
GD[to].push_back(from);
}
}
for(int i=0;i<V;++i)dfs(i);
for(int i=0;i<V;++i)marked[i] = false;
for(int i=sortOrder.size()-1;i>=0;--i){
if(!marked[sortOrder[i]])groupNo++;
dfs2(sortOrder[i]);
}

vector<int> ans;
for(int i=0;i<res.size();++i){
if(res[i].size()>1){
int group = i;
bool flag = true;
for(int j=0;j<res[i].size();++j){
for(int k=0;k<G[res[group][j]].size();++k){
if(reg[G[res[group][j]][k]]!=group){
flag = false;
break;
}
}
if(!flag)break;
}
if(flag){
for(int j=0;j<res[i].size();++j)ans.push_back(res[i][j]);
}
}else if(res[i].size()==1){
if(G[res[i][0]].size()==0)ans.push_back(res[i][0]);
else if(G[res[i][0]].size()==1 && G[res[i][0]][0]==res[i][0])ans.push_back(res[i][0]);
}
}
std::sort(ans.begin(), ans.end());
for(int i=0;i<ans.size();++i){
printf("%d ", ans[i]+1);
}
printf("\n");
}
}```