#include <iostream>
#include <vector>
#include <stack>

#include "Graph.h"
#include "Graph.cpp"

using namespace std;

int vizitat[100]={0};

/* CTC with Tarjan */
void tarjan(Graph & graph)
{
	std::vector<int> idx;
	std::vector<int> lowlink;
	std::stack<int> st;

	/* TODO: initialization needed by Kosaraju and DFS calls */
}

/* DFS */
void dfs(Graph graph,int nod, stack<int> &st)
{
	/* TODO: write a version of DFS depending on your algorithm of choice (Tarjan or Kosaraju) */
	vizitat[nod]=1;

	vector<int> vecini;
	vecini=graph.get_neighbours(nod);

	for(int i=0; i<vecini.size(); i++)
        if(vizitat[vecini[i]]==0)
            dfs(graph,vecini[i],st);

    st.push(nod);

}

void dfsT(Graph graph,int nod)
{
    vector<int> vecini;
    vecini=graph.get_transposed_neighbours(nod);

    for(int i=0; i<vecini.size(); i++)
        if(vizitat[vecini[i]]==0)
            dfsT(graph,vecini[i]);
}

/* CTC with Kosaraju */
void kosaraju(Graph & graph)
{
	std::vector<int> color;
	std::stack<int> st;

	/* TODO: initialization needed by Kosaraju and DFS calls */

    int n=graph.get_n();

    int sw=1;
    while(sw)
    {
        sw=0;
        for(int i=0; i<n; i++)
            if(vizitat[i]==0)
            {
                dfs(graph,i,st);
                sw=1;
            }
    }
    for(int i=0; i<n; i++)
        vizitat[i]=0;

    int nr=0;
    while(!st.empty())
    {
        int v=st.top();
        st.pop();

        if(vizitat[v]==0)
        {
            //cout<<"Compon "<<nr<<endl;
            dfsT(graph,v);
            nr++;
        }

    }


}

int main()
{
    ifstream fin("ctc.in");
	/* get the size of the graph */
	int graph_size;
	fin >> graph_size;

	/* create a graph and initialize it with data read from the command line */
	Graph graph(graph_size);
	fin >> graph;

	fout << graph << "The strongly connected components are:" << std::endl;

	/* run one of the following algorithms on the graph */
	kosaraju(graph);
	//tarjan(graph);

	return 0;
}