Cod sursa(job #301932)

Utilizator snaked31Stanica Andrei snaked31 Data 8 aprilie 2009 15:39:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;


#define nm 100010


vector <int> v[nm], sol[nm];
stack <int> q;
vector <int>::iterator j;

int n, m, i, nrctc, x, y;
int ind[nm], indx, ll[nm], inq[nm];


inline int mn(int a, int b) { return (a < b ? a : b); }

void tarjan(int p)

{
	vector <int>::iterator it;
	ind[p] = indx;
	ll[p] = indx;
	++indx;
	q.push(p);
	inq[p] = 1;

	for(it=v[p].begin(); it!=v[p].end(); ++it)
	{
		if (ind[*it] == -1)
		{
			tarjan(*it);
			ll[p] = mn(ll[p], ll[*it]);
		}
		else
		if (inq[*it])
		{
			ll[p] = mn(ll[p], ll[*it]);
		}
	}
	if (ll[p] == ind[p])
	{
		int tmp;
		++nrctc;
		do 
		{
			tmp = q.top();
			sol[nrctc].push_back(tmp);
			q.pop();
			inq[tmp] = 0;
		}
		while (tmp != p);
	}


}


int main()

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

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


	for (i=1; i<=n; ++i)
	{
		ind[i] = -1;
	}
	indx = 0;
	
	for (i=1; i<=m; ++i)
	{
		scanf("%d %d ", &x, &y);
		v[x].push_back(y);
	}


	for (i=1; i<=n; ++i)
	{
		if (ind[i] == -1)
		{
			tarjan(i);
		}
	}

	printf("%d\n", nrctc);
	for (i=1; i<=nrctc; ++i)
	{
		for (j=sol[i].begin(); j!=sol[i].end(); ++j)
		{
			printf("%d ", *j);
		}
		printf("\n");
	}

	return 0;
}