Cod sursa(job #253323)

Utilizator floringh06Florin Ghesu floringh06 Data 5 februarie 2009 17:50:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "ctc.in"
#define FOUT "ctc.out"
#define MAX_N 100005

typedef struct NOD
{
	int nod;
	NOD *next;
};

NOD *G[MAX_N];
NOD *Gt[MAX_N];
unsigned char V[MAX_N];
int P[MAX_N];
int cnt;
int res;

int N, M;

	void readdata ()
	{
		int i, a, b;
		scanf ("%d %d", &N, &M);
		for (i = 1; i <= M; ++i)
		{
			scanf ("%d %d", &a, &b);
			NOD *q = new (NOD);
			q->nod = b, q->next = G[a], G[a] = q;			
			NOD *p = new (NOD);
			p->nod = a, p->next = Gt[b], Gt[b] = p;
		}
	}

	void DFSt (int nod)
	{
		V[nod] = 0;
		for (NOD *q = Gt[nod]; q != NULL; q = q->next)
			if (V[q->nod]) DFSt (q->nod);
	}	

	void DFSta (int nod)
	{
		V[nod] = 0;
		printf ("%d ", nod);
		for (NOD *q = Gt[nod]; q != NULL; q = q->next)
			if (V[q->nod]) DFSta (q->nod);
	}	

	void DFS (int nod)
	{
		V[nod] = 1;
		for (NOD *q = G[nod]; q != NULL; q = q->next)
			if (!V[q->nod]) DFS (q->nod);
		P[++cnt] = nod;
	}

	void solve ()
	{
		int i;
		for (i = 1; i <= N; ++i)
			if (!V[i]) DFS (i);
		for (i = N; i; --i)
			if (V[P[i]])
			{
				++res;
				DFSt(P[i]);
			}
		printf ("%d\n", res);
		memset (V, 1, sizeof (V));
		for (i = N; i; --i)
			if (V[P[i]])
			{
				++res;
				DFSta(P[i]);
				printf ("\n");
			}

	}

	int main ()
	{
		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);
		readdata ();
		solve ();

		return 0;
	}