Cod sursa(job #493781)

Utilizator DanutzRusu Dan Andrei Danutz Data 19 octombrie 2010 16:27:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
int n,m,a[100][100],s[100],p[100],nrc;
FILE *f,*g;
void cit(){
	int i,j,k;
	f=fopen("ctc.in","r");
	fscanf(f,"%d %d",&n,&m);
	for (k=1;k<=m;++k)
	{
		fscanf(f,"%d %d",&i,&j);
		a[i][j]=1;
	}
	fclose(f);
}

void ad1(int k){
	int i;
	s[k]=nrc;
	for (i=1;i<=n;++i)
		if (s[i]==0&&a[k][i]==1)
			ad1(i);
}

void ad2(int k){
	int i;
	p[k]=nrc;
	for (i=1;i<=n;++i)
		if (p[i]==0&&a[i][k]==1)
			ad2(i);
}

void afis(){
	int i,j;
	g=fopen("ctc.out","w");
	for (i=1;i<nrc;i++)
	{ //fprintf(g,"Comp nr:%d\n",i);
	  for (j=1;j<=n;j++)
		  if (s[j]==i)
			  fprintf(g,"%d ",j);
	   fputc('\n',g);
	}
	fclose(g);
}

void solve(){
	int i,j;
	nrc=1;
	for (i=1;i<=n;++i)
		if (s[i]==0)
		{
			s[i]=nrc;
			ad1(i); ad2(i);
			for (j=1;j<=n;j++)
				if (s[j]!=p[j])
					s[j]=p[j]=0;
			nrc++;	
		}
	afis();
}

int main(){
	cit();
	solve();
	return 0;
}