Cod sursa(job #778157)

Utilizator tm_raduToma Radu tm_radu Data 14 august 2012 01:13:54
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 100001
#define EMAX 200001

enum color { NEW, DISCOVERED, PROCESSED };

int n, m;
int i, j, k, colMax;
color s[NMAX];
vector<int> e[NMAX], eb[NMAX];
int c[NMAX];
int sol[NMAX], numSol;
int st[NMAX], stSize;

void DFS(int node);
void DFSB(int node);

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

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

	for (k = 1; k <= m; k++)
	{
		scanf("%d %d", &i, &j);
		e[i].push_back(j);
		eb[j].push_back(i);
	}

	for (k = 1; k <= n; k++)
		if (s[i] == NEW)
			DFS(k);

	for (k = 1; k <= n; s[k] = NEW, k++);

	for (k = n; k >= 1; k--)
		if (s[st[k]] == NEW)
		{
			colMax++;
			DFSB(st[k]);
		}

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

	for (k = 1; k <= n; k++)
	{
		if (k > 1 && c[sol[k]] != c[sol[k-1]]) printf("\n");
		printf("%d ", sol[k]);
	}

	return 0;
}

void DFS(int node)
{
	if (s[node] != NEW) return;
	s[node] = DISCOVERED;

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

	stSize++;
	st[stSize] = node;
	s[node] = PROCESSED;
}

void DFSB(int node)
{
	if (s[node] != NEW) return;
	s[node] = DISCOVERED;
	c[node] = colMax;
	numSol++;
	sol[numSol] = node;

	for (vector<int>::iterator it = eb[node].begin(); it != eb[node].end(); ++it)
		if (s[*it] == NEW)
			DFSB(*it);

	s[node] = PROCESSED;
}