Cod sursa(job #799833)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 20 octombrie 2012 10:31:19
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#define dim 1000

int n,m,i,j,k,V[dim][dim],nr,a,b,Fr[dim];

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

void read(){
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d",&a,&b);
		V[a][b]=1;
	}
}


void print(int x){
	int Z[dim],i;
	Z[0]=0;
	if(Fr[x]){
		print(x+1);
		return;
	}
	if(x==n+1){
		fprintf(g,"%d\n",nr);
		return;
	}
	for(i=1;i<=n;i++)
		if(V[i][x]&&V[x][i]){
			Z[++Z[0]]=i;
			Fr[i]=1;
		}
	if(Z[0])
		nr++;
	print(x+1);
	if(Z[0]){
		fprintf(g,"%d ",x);
		for(i=1;i<=Z[0];i++)
			fprintf(g,"%d ",Z[i]);
		fprintf(g,"\n");
	}
}

int main(){
	
	read();
	
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				if(i!=j&&V[i][k]&&V[k][j]){
					V[i][j]=1;
				}
			}
		}
	}
	
	print(1);
	
	return 0;
}