Cod sursa(job #330294)

Utilizator irene_mFMI Irina Iancu irene_m Data 9 iulie 2009 14:10:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream.h>
#define MaxN 20009
#define MaxM 200009

ofstream fout("ctc.out");

int n,s[MaxN],T[2][2*MaxM],suc[MaxN],pred[MaxN],nrc,a[MaxN][MaxN],m;

void add(int x,int y,int &st)
{
	T[0][st]=y;
	T[1][st]=s[x];
	s[x]=st;
	a[x][y]=1;
	st++;
}

void cit()
{
	int i,j,st=1;
	ifstream fin("ctc.in");
	fin>>n>>m;
	while(fin>>i>>j)
	{
		add(i,j,st);

	}
	fin.close();
}

void DF_p(int nod,int nrc)
{
	int k;
	pred[nod]=nrc;
	for(k=1;k<=n;k++)
		if(a[k][nod] && !pred[k])
			DF_p(k,nrc);
}

void DF_s(int nod,int nrc)
{
	int p=s[nod];
	suc[nod]=nrc;
	while(p)
	{
		if(!suc[T[0][p]])
			DF_s(T[0][p],nrc);
		p=T[1][p];
	}
}	

void afis(int p)
{
	for(int i=1;i<=n;i++)
		if(suc[i]==p && pred[i]==p)
			fout<<i<<" ";
	fout<<'\n';
}

int main()
{
	cit();
	for(int i=1;i<=n;i++)
	{
		if(!suc[i])
		{
			nrc++;
			DF_s(i,nrc);
			DF_p(i,nrc);
		}
		for(int j=1;j<=n;j++)
			if(suc[j]!=pred[j])
				suc[j]=pred[j]=0;
	}
	fout<<nrc<<'\n';
	for(int i=1;i<=nrc;i++)
		afis(i);
	fout.close();
	return 0;
}