Cod sursa(job #711426)

Utilizator ms-ninjacristescu liviu ms-ninja Data 12 martie 2012 08:45:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define dim 100005
int n, m;

vector <int> g[dim], gt[dim],sol[dim];
int postviz[dim],viz[dim],nrc,ctc;

void read()
{
	int i, a, b;
	
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>a >>b;
		g[a].push_back(b);
		gt[b].push_back(a);
	}
}

void df(int nod)
{
	vector <int> ::iterator it;
	viz[nod]=1;
	
	for(it=g[nod].begin();it!=g[nod].end();++it)
		if(viz[*it]==0)
			df(*it);
		
	postviz[++nrc]=nod;
}

void dft(int nod)
{
	vector <int> ::iterator it;
	viz[nod]=0;
	sol[ctc].push_back(nod);
	for(it=gt[nod].begin();it!=gt[nod].end();++it)
		if(viz[*it]==1)
			dft(*it);
		
}


void solve()
{
	int i;
	for(i=1;i<=n;++i)
		if(viz[i]==0)
			df(i);
		
	for(i=n;i>=1;--i)
		if(viz[postviz[i]]==1)
		{
			++ctc;
			dft(postviz[i]);
		}
		
}

void print()
{
	vector <int> ::iterator it;
	fout<<ctc <<'\n';
	
	for(int i=1;i<=ctc;++i)
	{
		for(it=sol[i].begin();it!=sol[i].end();++it)
			fout<<*it <<" ";
		fout<<'\n';
	}
}

int main()
{
	read();
	solve();
	print();
	return 0;
}