Cod sursa(job #796591)

Utilizator lianaliana tucar liana Data 11 octombrie 2012 21:16:11
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<stdio.h>
#define nmax 100005
#define mmax 200005
struct muchie{long x, y;};
long n, m, i, poz, tac, comp, j;
long rez[nmax], gr[nmax], pozinc[nmax], pozac[nmax], pozinct[nmax], pozact[nmax], ma[mmax], mat[mmax], viz[nmax], vf[nmax], grt[nmax];
muchie v[nmax];

void citire()
{
	scanf("%ld %ld",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld",&v[i].x,&v[i].y);
		gr[v[i].x]++;	grt[v[i].y]++;
	}
	pozinc[1]=pozac[1]=1;	pozinct[1]=pozact[1]=1;
	for (i=2;i<=n;i++)
	{	
		pozinc[i]=pozinc[i-1]+gr[i-1];	pozac[i]=pozinc[i];	
		pozinct[i]=pozinct[i-1]+grt[i-1];	pozact[i]=pozinct[i];
	}
	for (i=1;i<=m;i++)
	{	
		ma[pozac[v[i].x]]=v[i].y;	pozac[v[i].x]++;	
		mat[pozact[v[i].y]]=v[i].x;	pozact[v[i].y]++;
	}
}

void dfs1(long nod)
{
	long i;
	viz[nod]=1;
	for (i=pozinc[nod];i<=pozinc[nod]+gr[nod]-1;i++)
		if (viz[ma[i]]==0)
			dfs1(ma[i]);
	vf[++tac]=nod;
}

void dfs2(long nod)
{
	long i;
	viz[nod]=2;
	for (i=pozinct[nod];i<=pozinct[nod]+grt[nod]-1;i++)
		if (viz[mat[i]]<2)
			dfs2(mat[i]);
	rez[++poz]=nod;
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	for (i=1;i<=n;i++)
		if (!viz[i])
			dfs1(i);
	for (i=n;i>=1;i--)
		if (viz[vf[i]]<2)
		{
			comp++;	
			dfs2(vf[i]);
			poz++;
		}
	printf("%ld\n",comp);
	poz=1;
	for (i=1;i<=comp;i++)
	{
		while (rez[poz]!=0)
		{	printf("%ld ",rez[poz]);	poz++;	}
		poz++;
		printf("\n");
	}
	return 0;
}