Cod sursa(job #571180)

Utilizator edward_alexStanciu Alexandru Marian edward_alex Data 4 aprilie 2011 09:49:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<iostream>
#include<fstream>
#include<list>

using namespace std;

list<int> a[10000];
list<int> b[10000];
list<int> c[10000];

void dfsN(list<int> *l,int vf,list<int> stiva,int *color)
{
	color[vf] = 1;
	list<int>::iterator it;
	for(it = l[vf].begin() ; it != l[vf].end() ; it++)
		if(color[*it] == 0)
			dfsN(l,*it,stiva,color);
	stiva.push_front(vf);
	color[vf] = 2;
}

void dfsT(list<int> *l,int vf,list<int> stiva,int *color)
{
	color[vf] = 1;
	stiva.push_front(vf);
	list<int>::iterator it;
	for(it = l[vf].begin() ; it != l[vf].end() ; it++)
		if(color[*it] == 0)
			dfsN(l,*it,stiva,color);
	color[vf] = 2;
}

void ctc(list<int> *a,list<int> *c,list<int> stiva,int n)
{
	int *color = new int[n + 1];
	for(int i = 1 ; i <= n ;i++)
		color[i] = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		if(color[i] == 0)
			dfsN(a,i,stiva,color);
	}
	for(int i = 1 ; i <= n ;i++)
		color[i] = 0;
	int l = 1;
	while(stiva.empty() != true)
	{
		int p = stiva.front();
		stiva.pop_front();
		if(color[p] == 0)
			dfsT(c,p,b[l],color);
		l++;
	}
	fstream out("ctc.out",ios::out);
	for(int i = 1 ; i <= l ; i++)
	{
		list<int>::iterator it;
		for(it = b[i].begin() ; it != b[i].end() ; it++)
			out<<*it<<" ";
		out<<endl;
	}
}

int main()
{
	fstream in("ctc.in",ios::in);
	int n,m;
	in>>n;
	in>>m;
	for(int i = 1 ; i <= m ; i++)
	{
		int k1,k2;
		in>>k1;
		in>>k2;
		a[k1].push_front(k2);
		c[k2].push_front(k1);
	}
	list<int> stiva;
	ctc(a,c,stiva,n);
	return 0;
}