Cod sursa(job #416226)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 12 martie 2010 13:13:52
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100010

int n, index, idx[nmax], low[nmax], cnt;
vector <int> g[nmax], ctc[nmax];
stack <int> s;

void tarjan(int nod)
{
	int i;
	idx[nod]=low[nod]=++index;
	s.push(nod);
	for (i=0; i<g[nod].size(); i++)
	{
		if (!idx[g[nod][i]]) tarjan(g[nod][i]);
		if (idx[g[nod][i]]>=0)
			low[nod]=min(low[nod], low[g[nod][i]]);
	}
	if (low[nod]==idx[nod])
	{
		cnt++;
		do
		{
			i=s.top();
			ctc[cnt].push_back(i);
			idx[i]=-1;
			s.pop();
		}
		while (i!=nod);
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	int m, i, j, x, y;
	scanf("%d %d",&n,&m);
	while (m--)
	{
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
	}
	for (i=1; i<=n; i++)
		if (!idx[i]) tarjan(i);
	printf("%d\n",cnt);
	for (i=1; i<=cnt; i++)
	{
		for (j=0; j<ctc[i].size(); j++) printf("%d ",ctc[i][j]);
		printf("\n");
	}
}