## Sunday, May 24, 2015

### CAPCITY SPOJ.com solution C++

Problem : spoj.com/problems/CAPCITY

Algorithm : Kosaraju's Algorithm ( Two pass, Strongly connected components, kernel dag )

Source: (C++ : AC)

```#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<vector<int> > SCCconn;

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;
}

void dfs3(int callingGroup, int vertex){
if(marked[vertex]){
if(callingGroup!=reg[vertex])SCCconn[callingGroup].push_back(reg[vertex]);
return;
}
marked[vertex] = true;
for(int i=0;i<GD[vertex].size();++i){
dfs3(callingGroup, GD[vertex][i]);
}
}

int dfs4(int callingGroup){
int size=0;
for(int i=0;i<SCCconn[callingGroup].size();++i){
size+=dfs4(SCCconn[callingGroup][i]);
}
size+=res[callingGroup].size();
return size;
}

int main(){
scanf("%d %d", &V, &E);
marked = new bool[V];
reg = new int[V];

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

for(int i=0;i<V;++i){
vector<int> x,xx,xxx,xxxx;
res.push_back(x);
G.push_back(xx);
GD.push_back(xxx);
SCCconn.push_back(xxxx);
}

for(int i=0;i<E;++i){
int from, to;
scanf("%d %d", &from, &to);
from--;to--;
G[from].push_back(to);
GD[to].push_back(from);
}

if(V==1){
printf("%d\n%d", 1, V);
return 0;
}
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> result;
for(int i=0;i<V;++i)marked[i] = false;
for(int i=0;i<V;++i){
if(res[i].size()==0)break;
for(int j=0;j<res[i].size();++j){
dfs3(i, res[i][j]);
}
}

for(int i=0;i<SCCconn.size();++i){
int sizeOfGroup = dfs4(i);
if(sizeOfGroup==V){
for(int j=0;j<res[i].size();++j){
result.push_back(res[i][j]);
}
}
}
printf("%d\n", result.size());
sort(result.begin(), result.end());

for(int i=0;i<result.size();++i)printf("%d ", result[i]+1);
printf("\n");
}```