Cod sursa(job #1087483)

Utilizator federerUAIC-Padurariu-Cristian federer Data 19 ianuarie 2014 14:47:34
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 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];
vector<int>postord(Nmax+1);
int N, M, i, n, comp[Nmax], 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[nod] = nrc;
	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]] && !comp[postord[i]])
	{
		nrc++;
		DFS(postord[i]);
	}
	fout << nrc << '\n';
	for (i = 1; i <= nrc; ++i)
	{
		for (int j = 1; j <= N; ++j)
		if (comp[j] == i)
			fout << j << ' ';
		fout << '\n';
	}
	return 0;
}