Cod sursa(job #633591)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 14 noiembrie 2011 03:34:56
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>

using namespace std;

int a[10000][10000],viz[10000001],n,m;

void adancime(int v)
{	long int vf,st[10000],primul,j,k;
	vf=1;
	st[vf]=v;
	viz[v]=1;
	while(vf>=1)
	{	primul=st[vf];
		k=0;
		for(j=1;j<=n&&k==0;j++)
			if(a[primul][j]==1&&viz[j]==0)
				k=1;
		if(k==1) {
			j--;vf++;st[vf]=j;viz[j]=1;}
		else
			vf--;
	}
}

int main()
{	long int i,x,y,conexe=0;
	FILE *c,*d;
	c=fopen("dfs.in","r");
	d=fopen("dfs.out","w");
	fscanf(c,"%ld %ld",&n,&m);
	for(i=1;i<=m;i++)
	{	fscanf(c,"%ld %ld",&x,&y);
		a[x][y]=1;
		a[y][x]=1;	}
	for(i=1;i<=n;i++)
		if(viz[i]==0)
		{	adancime(i);
			conexe++;	}
	fprintf(d,"%ld",conexe);
	fclose(c);
	fclose(d);	}