Pagini recente » Cod sursa (job #347579) | Cod sursa (job #1001888) | Cod sursa (job #580846) | Cod sursa (job #41589) | Cod sursa (job #159745)
Cod sursa(job #159745)
#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);
}