Cod sursa(job #288704)

Utilizator stinkyStinky si Grasa stinky Data 26 martie 2009 01:03:58
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;

const int N = 100005;

vector<int> a[N];
vector<int> c[N];
bool ins[N];

stack<int> stiva;

int n,ind[N],sub[N],index,nrc;

inline int minim(int x,int y)
{
	return x < y ? x : y ;
}

void citire()
{
	int m,x,y;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
	}
}

void dfs(int x)
{
	ind[x] = ++index;
	stiva.push(x);
	ins[x] = true;
	sub[x] = index;
	int nr = a[x].size(),y;
	for(int i=0 ; i<nr ; ++i)
	{
		y=a[x][i];
		if(ind[y] == 0 || ins[y])
		{
			if(ind[y] == 0)
				dfs(y);
			sub[x] = minim(sub[x],sub[y]);
		}
	}
	if(sub[x] == ind[x])
	{
		++nrc;
		do
		{
			y=stiva.top();
			stiva.pop();
			c[nrc].push_back(y);
			ins[y] = false;
		}
		while(y != x);
	}
}

void componente()
{
	int nr;
	for(int i=1 ; i<=n ; ++i)
		if(ind[i] == 0)
			dfs(i);
	printf("%d\n",nrc);
	for(int i=1 ; i<=nrc ; ++i)
	{
		nr = c[i].size();
		for(int j=0 ; j<nr ; ++j)
			printf("%d ",c[i][j]);
		printf("\n");
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	componente();
	return 0;
}