Cod sursa(job #485667)

Utilizator raduzerRadu Zernoveanu raduzer Data 19 septembrie 2010 07:56:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
using namespace std;

#define pb push_back
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

const int MAX_N = 100001;

int n, m, nr_sol, z;
int a[MAX_N];
char f[MAX_N];
vector <int> v[MAX_N], vt[MAX_N], sol[MAX_N];

void df(int nod)
{
	if (f[nod])
		return;
	f[nod] = 1;

	forit(it, v[nod])
		df(*it);

	a[++z] = nod;
}

void df2(int nod)
{
	if (f[nod] == 2)
		return;
	f[nod] = 2;

	sol[nr_sol].pb(nod);

	forit(it, vt[nod])
		df2(*it);
}

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

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

	for (i = 1; i <= m; ++i)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		v[x].pb(y);
		vt[y].pb(x);
	}

	for (i = 1; i <= n; ++i)
		if (!f[i])
			df(i);

	for (i = n; i; --i)
		if (f[a[i]] != 2)
		{
			++nr_sol;
			df2(a[i]);
		}

	printf("%d\n", nr_sol);

	for (i = 1; i <= nr_sol; ++i)
	{
		forit(it, sol[i])
			printf("%d ", *it);

		printf("\n");
	}
}