Cod sursa(job #1095954)

Utilizator pulseOvidiu Giorgi pulse Data 1 februarie 2014 12:03:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

#define NMAX 100003

int n, m, count, ksol, index[NMAX], lp[NMAX];
vector <int> v[NMAX], sol[NMAX];
stack <int> s;
bool used[NMAX];

void ReadData ()
{
	scanf ("%d %d", &n, &m);
	for (int i = 1, a, b; i <= m; ++i)
	{
		scanf ("%d %d", &a, &b);
		v[a].push_back (b);
	}
}

void Tarjan (int k)
{
	++count;
	index[k] = count;
	lp[k] = count;
	s.push (k);
	used[k] = true;
	for (int i = 0; i < v[k].size (); ++i)
	{
		if (index[v[k][i]] == 0)
		{
			Tarjan (v[k][i]);
			if (lp[v[k][i]] < lp[k])
				lp[k] = lp[v[k][i]];
		}
		else if (used[v[k][i]] && lp[v[k][i]] < lp[k])
			lp[k] = lp[v[k][i]];
	}
	if (index[k] == lp[k])
	{
		++ksol;
		while (s.top () != k)
		{
			used[s.top ()] = false;
			sol[ksol].push_back (s.top ());
			s.pop ();
		}
		used[s.top ()] = false;
		sol[ksol].push_back (s.top ());
		s.pop ();
	}
}

int main ()
{
	freopen ("ctc.in", "r", stdin);
	freopen ("ctc.out", "w", stdout);
	ReadData ();
	for (int i = 1; i <= n; ++i)
	{
		if (index[i] == 0)
			Tarjan (i);
	}
	printf ("%d\n", ksol);
	for (int i = 1; i <= ksol; ++i)
	{
		for (int j = 0; j < sol[i].size (); ++j)
			printf ("%d ", sol[i][j]);
		printf ("\n");
	}
	return 0;
}