Cod sursa(job #304112)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 10 aprilie 2009 23:05:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 100010
#define pb push_back

using namespace std;

int n, m;
vector <int> stackCtc;
vector <int> listDrum[MAX], listDrumTr[MAX];
vector <vector <int> > compBic;
vector <int> vctComp;
int enq[MAX];

inline void dfs(int nod)
{
	if (enq[nod])
		return;
	enq[nod] = 1;

	for (int i = 0; i < listDrum[nod].size(); i++)
		dfs(listDrum[nod][i]);

	stackCtc.pb(nod);
}

inline void dfsConstr(int nod)
{
	if (!enq[nod])
		return;
	enq[nod] = 0;

	for (int i = 0; i < listDrumTr[nod].size(); i++)
		dfsConstr(listDrumTr[nod][i]);

	vctComp.pb(nod);
}

int main()
{
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (; m; m--)
	{
		int nod1, nod2;
		scanf("%d %d", &nod1, &nod2);

		listDrum[nod1].pb(nod2);
		listDrumTr[nod2].pb(nod1);
	}

	// Dfs 1
	for (int i = 1; i <= n; i++)
		dfs(i);

	// Dfs 2
	for (; !stackCtc.empty(); stackCtc.pop_back())
	{
		dfsConstr(stackCtc[stackCtc.size() - 1]);

		if (!vctComp.empty())
			compBic.pb(vctComp);
		vctComp.clear();
	}

	printf("%d\n", compBic.size());
	for (int i = 0; i < compBic.size(); i++)
	{
		for (int j = 0; j < compBic[i].size(); j++)
			printf("%d ", compBic[i][j]);
		printf("\n");
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}