Cod sursa(job #778168)

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

enum state {NEW, INSTACK, DONE};

int n, m;
int i, j, k, maxCol, index;
state s[NMAX];
vector<int> e[NMAX];
int c[NMAX], low[NMAX], t[NMAX];
int sol[NMAX], solSize;
stack<int> st;

void DFS(int node);
void Color(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);
	}

	for (k = 1; k <= n; k++)
		if (s[k] == NEW)
			DFS(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] != NEW) return;
	s[node] = INSTACK;
	t[node] = ++index;
	low[node] = index;
	st.push(node);

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

	if (low[node] == t[node])
		Color(node);
}

void Color(int node)
{
	++maxCol;
	while (st.top() != node)
	{
		int v = st.top();
		s[v] = DONE;
		c[v] = maxCol;
		st.pop();
		sol[++solSize] = v;
	}
	s[st.top()] = DONE;
	c[st.top()] = maxCol;
	sol[++solSize] = st.top();
	st.pop();
}