Cod sursa(job #384779)

Utilizator Mishu91Andrei Misarca Mishu91 Data 20 ianuarie 2010 22:11:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

#define MAX_N 100005
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

int N, M, Nrc, S[MAX_N];
vector <int> Gin[MAX_N], Gout[MAX_N], C[MAX_N];
bitset <MAX_N> viz;

void citire()
{
	fin >> N >> M;

	for(int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >> x >> y;

		Gout[x].push_back(y);
		Gin[y].push_back(x);
	}
}

void DFP(int nod)
{
	viz[nod] = 1;

	foreach(Gout[nod])
		if(viz[*it] == 0)
			DFP(*it);

	S[++S[0]] = nod;
}

void DFM(int nod)
{
	viz[nod] = 1;
	C[Nrc].push_back(nod);

	foreach(Gin[nod])
		if(viz[*it] == 0)
			DFM(*it);
}

void solve()
{
	for(int i = 1; i <= N; ++i)
		if(viz[i] == 0)
			DFP(i);

	viz.reset();

	for(int i = S[0]; i; --i)
		if(viz[S[i]] == 0)
		{
			++Nrc;
			DFM(S[i]);
		}

	fout << Nrc << "\n";
	for(int i = 1; i <= Nrc; ++i)
	{
		foreach(C[i])
			fout << *it << " ";
		fout << "\n";
	}
}

int main()
{
	citire();
	solve();
}