Cod sursa(job #711467)

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