Cod sursa(job #159745)

Utilizator cosserBula Ionut cosser Data 14 martie 2008 12:57:54
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define NMax 100000


typedef struct {int x,y;}muchie;
long n,m;
muchie G[NMax];
int C[NMax];

void citire();
void descomp();
void afisare();

int main()
{citire();
 descomp();
 afisare();
 return 0;}

void citire()
{
FILE * fin =fopen("dfs.in","r");
int i;
fscanf(fin,"%d %d",&n,&m);
for(i=0;i<m;i++)
  fscanf(fin, "%d %d", &G[i].x, &G[i].y);
}

void descomp()
{int i,j,min,max;
for(i=1;i<=n;i++)C[i]=i;
for(j=0;j<m;j++)
	if(C[G[j].x]!=C[G[j].y])
	  {if(C[G[j].x]<C[G[j].y])min=C[G[j].x],max=C[G[j].y];
	     else min=C[G[i].y],max=C[G[j].x];
	    for(i=1;i<=n;i++)if(C[i]==max)C[i]=min;
	  }

}

void afisare()
{
int nrc=0,i,j;
for(i=1;i<=n;i++)
   if(C[i])
 { nrc++;
   for(j=i+1;j<=n;j++)
   if(C[i]==C[j])  C[j]=0;  }
     
FILE *fout = fopen ("dfs.out","w");
fprintf(fout,"%d",nrc);
}