Cod sursa(job #1087488)

Utilizator federerUAIC-Padurariu-Cristian federer Data 19 ianuarie 2014 14:52:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
#define Nmax 100010
using namespace std;

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

vector<int>G[Nmax], GT[Nmax], comp[Nmax];
vector<int>postord(Nmax+1);
int N, M, i, n, nrc;
bool viz[Nmax];

void DFSpostord(int nod)
{
	int i, vecin;
	viz[nod] = 1;
	for (i = 0; i < G[nod].size(); ++i)
	{
		vecin = G[nod][i];
		if (!viz[vecin])
			DFSpostord(vecin);
	}
	postord[++n] = nod;
}

void DFS(int nod)
{
	int i, vecin;
	viz[nod] = 0; comp[nrc].push_back(nod);
	for (i = 0; i < GT[nod].size(); ++i)
	{
		vecin = GT[nod][i];
		if (viz[vecin])
		DFS(vecin);
	}
}

int main()
{
	int x, y;
	fin >> N >> M;
	for (i = 1; i <= M; ++i)
	{
		fin >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}

	for (i = 1; i <= N;++i)
		if (!viz[i])
			DFSpostord(i);

	for (i = N; i >= 1;--i)
	if (viz[postord[i]])
	{
		nrc++;
		DFS(postord[i]);
	}
	fout << nrc << '\n';
	for (i = 1; i <= nrc; ++i)
	{
		for (int j = 0; j<comp[i].size();++j)
			fout << comp[i][j] << ' ';
		fout << '\n';
	}
	return 0;
}