Pagini recente » Cod sursa (job #589011) | Cod sursa (job #2187210) | Cod sursa (job #507132) | Clasamentul arhivei de probleme | Cod sursa (job #462288)
Cod sursa(job #462288)
#include<stdio.h>
using namespace std;
#define dim 101
#define dim2 dim*(dim-1)/2
typedef struct {int x,y;} Muchie;
Muchie G[dim2];
int C[dim],n,m;
void citire();
void desc_comp_conexe();
void afisare();
int main()
{
citire();
desc_comp_conexe();
afisare();
return 0;
}
void citire()
{
FILE *f=fopen("dfs.in","r");
int i;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
fscanf(f,"%d %d",&G[i].x,&G[i].y);
fclose(f);
}
void desc_comp_conexe()
{
int i,j,min,max;
for(i=1;i<=n;i++)
C[i]=i;
for(j=1;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[j].y ], max=C[ G[j].x ];
for(i=1;i<=n;i++)
if( C[i]==max )
C[i]=min;
}
}
void afisare()
{
FILE *g=fopen("dfs.out","w");
int nrc=0,i,j;
for(i=1;i<=n;i++)
if(C[i])
{
nrc++;
//printf("componenta conexa %d: %d",nrc,i);
for(j=i+1;j<=n;j++)
if(C[j]==C[i])
{
// printf(" %d",j);
C[j]=0;
}
//printf("\n");
}
fprintf(g,"%d\n",nrc);
fclose(g);
}