Cod sursa(job #778161)

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

int n, m;
int i, j, k, maxCol;
int s[NMAX];
vector<int> e[NMAX], eb[NMAX];
int c[NMAX];
int sol[NMAX], solSize;
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[k] == 0)
			DFS(k);

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

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

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

	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] != 0) return;
	s[node] = 1;

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

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

void DFSB(int node)
{
	if (s[node] != 0) return;
	s[node] = 1;
	c[node] = maxCol;
	solSize++;
	sol[solSize] = node;

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