Cod sursa(job #723674)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 25 martie 2012 18:56:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define lung 100001
vector <int> v[lung],trans[lung],rasp[lung];
int n,m,i,ord[lung],nr,a,b;
bool viz[lung];
inline void df(int x)
{   vector <int>::iterator it;
	viz[x] = true;
	for (it=v[x].begin();it!=v[x].end();++it)
		if (!viz[*it])
			df(*it);
	ord[++nr] = x;
}
inline void dft(int x)
{   vector <int>::iterator it;
	viz[x] = false;
	rasp[nr].push_back(x);
	for (it=trans[x].begin();it!=trans[x].end();++it)
		if (viz[*it])
			dft(*it);
}
int main()
{   fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b;
	    v[a].push_back(b);
		trans[b].push_back(a);
	}
	for (i=1;i<=n;++i)
		if (!viz[i])
			df(i);
	nr = 0;
	for (i=n;i;--i)
	    if (viz[ord[i]])
		{   ++nr;
		    dft(ord[i]);
		}
	fout << nr << '\n';
	vector <int>::iterator it;
	for (;nr;--nr)
	{	for (it=rasp[nr].begin();it!=rasp[nr].end();++it)
			fout << *it << " ";
		fout << '\n';
    }
 	return 0;
}