Cod sursa(job #1450151)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 11 iunie 2015 18:04:15
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMax 100010

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int nodes, edges, inc, nrctc, postorder[NMax];
bool mark[NMax];
vector<int> G[NMax], Gr[NMax], sol[NMax];

void DFS(int node)
{
	mark[node] = true;

	for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++)
		if (!mark[*it])
			DFS(*it);

	postorder[++inc] = node;
}

void DFSk(int node)
{
	mark[node] = true;
	sol[nrctc].push_back(node);

	for (vector<int>::iterator it = Gr[node].begin(); it != Gr[node].end(); it++)
		if (!mark[*it])
			DFSk(*it);
}

int main()
{
	f >> nodes >> edges;

	int n1, n2;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2;

		G[n1].push_back(n2);
		Gr[n2].push_back(n1);
	}

	for (int i = 1; i <= nodes; i++)
		if (!mark[i])
			DFS(i);

	memset(mark, false, sizeof(mark));

	for (int i = nodes; i >= 1; i--) {
		if (!mark[postorder[i]]) {
			nrctc++;

			DFSk(postorder[i]);
		}
	}

	g << nrctc << "\n";


	for (int i = 1; i <= nrctc; i++) {
		for (vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); it++)
			g << *it<<" ";
		g << "\n";
	}

	return 0;
}