Cod sursa(job #796951)

Utilizator RaduDoStochitoiu Radu RaduDo Data 13 octombrie 2012 00:47:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define MAXN 100010
#define pb push_back
using namespace std;

vector<int> G[MAXN],GT[MAXN];
int nc,nr,i,k,n,m,x,y,St[MAXN];
bool sel[MAXN];

void DF(int x)
{
	int i;
	sel[x]=true;
	for(i=0;i<(int)G[x].size();++i)
		if(!sel[G[x][i]])
			DF(G[x][i]);
	St[++nr]=x;
}

void DFT(int x, bool k)
{
	int i;
	sel[x]=true;
	if(k)
		printf("%d ", x);
	for(i=0;i<(int)GT[x].size();++i)
		if(!sel[GT[x][i]])
			DFT(GT[x][i], k);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		G[x].pb(y);
		GT[y].pb(x);
	}
	
	memset(sel,false,sizeof(sel));
	for(i=1;i<=n;++i)
		if(!sel[i])
			DF(i);
		
	memset(sel,false,sizeof(sel));
	for(i=n;i>0;--i)
		if(!sel[St[i]])
		{
			DFT(St[i],false);
			nc++;
		}
		
	printf("%d\n", nc);
	memset(sel, false,sizeof(sel));
	for(i=n;i>0;--i)
		if(!sel[St[i]])
		{
			DFT(St[i], true);
			printf("\n");
		}
	return 0;
}