Cod sursa(job #462290)

Utilizator bugyBogdan Vlad bugy Data 10 iunie 2010 12:26:02
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
using namespace std;
#define dim 100005
#define dim2 200005

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);

}