Cod sursa(job #662852)

Utilizator madmanjonesJones the one madmanjones Data 17 ianuarie 2012 05:40:12
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>

#define MAX 100001


int t[2][MAX],nr=0,start[MAX],n,s[MAX];

void citire();
void afisare();
void df(int nod);



int main()
{
	citire();
	for (int k=1;k<=n;++k)
		if (s[k]==0)
		{
			++nr;
			df(k);
		}
	afisare();
return 0;
}

void citire()
{
	int i,j,k=0,x;
	FILE* file=fopen("dfs.in","r");
	fscanf(file,"%d %d\n",&n,&x);
	for(int a=0;a<x;++a)
	{
		fscanf(file,"%d %d\n",&i,&j);
		k++;
		t[0][k]=j;
		t[1][k]=start[i];
		start[i]=k;
		k++;
		t[0][k]=i;
		t[1][k]=start[j];
		start[j]=k;
	}
	fclose(file);
}



void afisare()
{
		FILE *file=fopen("dfs.out","w+");
		fprintf(file,"%d\n",nr);
		fclose(file);
}


void df(int nod)
{
	int p;
	p=start[nod];
	s[nod]=1;
	while (p)
	{
		if (s[t[0][p]]==0)
			df(t[0][p]);
		p=t[1][p];
	}
}