// implementare conform 
// Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest - "Introducere in Algoritmi"

#include <iostream.h>
#include <fstream.h>

#define ALB   1
#define GRI   2
#define NEGRU 3

#define N 100

void initializare (int **graf, int *n, char* nume_fisier,int* culoare, int* start, int* end, int* parinte, int* aux)
{
	fstream f (nume_fisier,ios::in);
	f>>(*n);
	int i,j;
	for (i=0;i<*n;i++)
		for (j=0;j<*n;j++)
			f>>graf[i][j];
	int k;
	for (k=0;k<*n;k++)
	{
		culoare[k]=0;
		start[k]=0;
		end[k]=0;
		parinte[k]=0;
		aux[k]=k+1;
	}
	f.close();
}

void deinitializare (int **graf, int n, int* culoare, int* start, int* end, int* parinte, int* aux)
{
	int i,j;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			graf[i][j]=0;
	int k;
	for (k=0;k<n;k++)
	{
		culoare[k]=0;
		start[k]=0;
		end[k]=0;
		parinte[k]=0;
		aux[k]=0;
	}
}

void vizitare (int n, int** graf, int u, int* culoare, int *start, int *end, int *parinte, int *timp)
{
	culoare[u]=GRI;
	start[u]=*timp;
	*timp=*timp+1;
	int v;
	for (v=0;v<n;v++)
		if (graf[u][v] && culoare[v]==ALB)
		{
			parinte[v]=u;
			vizitare (n,graf,v,culoare,start,end,parinte,timp);
		}
	culoare[u]=NEGRU;
	end[u]=*timp;
	*timp=*timp+1;
}

void parcurgere_adancime (int n, int **graf, int* culoare, int* start, int* end, int* parinte, int* timp)
{
	int k;
	for (k=0;k<n;k++)
	{
		culoare[k]=ALB;
		parinte[k]=-1;
	}
	*timp=1;
	for (k=0;k<n;k++)
		if (culoare[k]==ALB)
			vizitare (n,graf,k,culoare,start,end,parinte,timp);
}

void sortare_minmax (int n,int *v1,int *v2)
{
	int i,j,temp;
	for (i=0;i<n-1;i++)
		for (j=i+1;j<n;j++)
			if (v1[i]>v1[j])
			// interschimbare
			{
				temp=v1[i];
				v1[i]=v1[j];
				v1[j]=temp;
				temp=v2[i];
				v2[i]=v2[j];
				v2[j]=temp;
			}
}

void afisare (int n,int *v1,int *v2,char* nume_fisier)
{
	fstream g(nume_fisier,ios::out);
	int k;
	for (k=0;k<n;k++)
		g<<"nodul "<<(k+1)<<" : "<<v1[k]<<"/"<<v2[k]<<endl;
	g.close();
}

int main (int argc, char** argv)
{
	int **graf;
	int *culoare, *start, *end, *parinte;
	int *aux;
	int n;
	int timp;
	int k;	
	graf=new int* [N];
    for (k=0;k<N;k++)
		graf[k]=new int [N];
	culoare=new int [N];
	start=new int [N];
	end=new int [N];
	parinte=new int [N];
	aux=new int[N];
	// fisier 1
    initializare (graf,&n,"input1.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_1.txt");
	// fisier 2
    initializare (graf,&n,"input2.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_2.txt");
	// fisier 3
    initializare (graf,&n,"input3.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_3.txt");
	// fisier 4
    initializare (graf,&n,"input4.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_4.txt");
	// fisier 5
    initializare (graf,&n,"input5.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_5.txt");
	// fisier 6
    initializare (graf,&n,"input6.txt",culoare,start,end,parinte,aux);
	parcurgere_adancime (n,graf,culoare,start,end,parinte,&timp);
	//sortare_minmax(n,start,aux);
	afisare(n,start,end,"output_a_6.txt");
	return 0;
}