Cod sursa(job #311923)

Utilizator andreea_mandreea martinovici andreea_m Data 4 mai 2009 18:42:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<stdio.h>
#include<vector>
#define N 100007
#define M 200007
using namespace std;

int n,m,*a[N],*b[N],x[M],y[M],da[N],db[N],nrc=0,nr;

vector<int> c[N];
vector<int> v;

bool viz1[N],viz2[N];

void citire()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{	
		scanf("%d%d",&x[i],&y[i]);
		++da[x[i]];
		++db[y[i]];
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=new int[da[i]+1];
		b[i]=new int[db[i]+1];
		a[i][0]=b[i][0]=0;
	}
	for(int i=1;i<=m;i++)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
	    b[y[i]][++b[y[i]][0]]=x[i];
	}
}
/*
void afisare(int **a)
{
	for(int i=1;i<=n;i++)
	{
		printf("%d : %d varfuri : ",i,a[i][0]);
		for(int j=1;j<=a[i][0];j++)
			printf("%5d",a[i][j]);
		printf("\n");
	}
	printf("\n");
}
*/
void df1(int x)
{
	viz1[x]=true;
	v.push_back(x);
	for(int i=1;i<=a[x][0];++i)
		if(!viz1[a[x][i]])
			df1(a[x][i]);
}

void df2(int x)
{
	viz2[x]=true;
	c[nrc].push_back(x);
	for(int i=1;i<=b[x][0];++i)
		if(viz1[b[x][i]] && !viz2[b[x][i]])
			df2(b[x][i]);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	//afisare(a);
	//afisare(b);
	for(int i=1;i<=n;++i)
		if(!viz2[i])
		{
			df1(i);//marcheaza varfurile in care se poate ajunge din i si le adauga in v
			//parcurg v si determin comp tare conexe ale varfurilor sale
			nr=v.size();
			for(int j=1;j<nr;++j)
				if(!viz2[v[j]])
				{
					++nrc;
					df2(v[j]);
				}
		}
	printf("%d\n",nrc);
	for(int i=1;i<=nrc;++i)
	{
		for(int j=0;j<c[i].size();++j)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	return 0;
}