Cod sursa(job #245419)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 17 ianuarie 2009 23:01:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <assert.h>
#include <vector>

using namespace std;

#define maxn 100010

int N, M, L, NR;
vector <int> A[maxn], T[maxn];
int G[maxn], GT[maxn], S[maxn];
char u[maxn];
vector <int> CMP[maxn];

inline void DFS(int nod)
{
	int i;

	u[nod] = 1;

	for (i=0; i<G[nod]; i++)
		if (!u[A[nod][i]]) DFS(A[nod][i]);

	S[++L] = nod;
}

inline void DFS2(int nod)
{
	int i;

	u[nod] = 2;
	CMP[NR].push_back(nod);

	for (i=0; i<GT[nod]; i++)
		if (u[T[nod][i]] != 2) DFS2(T[nod][i]);
}

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

	int i, j, x, y;

	scanf("%d %d ", &N, &M);

//	assert(1<=N && N<=100000);
//	assert(1<=M && M<=200000);

	for (i=1; i<=M; i++)
	{
		scanf("%d %d ", &x, &y);

//		assert(1<=x && x<=N);
//		assert(1<=y && y<=N);

		A[x].push_back(y);
		T[y].push_back(x);
	}

	for (i=1; i<=N; i++) 
	{
		G[i] = A[i].size();
		GT[i] = T[i].size();
	}

	for (i=1; i<=N; i++) 
		if (!u[i]) DFS(i);

	for (i=N; i>0; i--)
		if (u[S[i]] != 2) 
		{	
			NR++;
			DFS2(S[i]);
		}

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

	for (i=1; i<=NR; i++)
	{
		L = CMP[i].size();
		for (j=0; j<L; j++) printf("%d ", CMP[i][j]);
		printf("\n");
	}

	return 0;
}