Cod sursa(job #531584)

Utilizator maritimCristian Lambru maritim Data 9 februarie 2011 22:02:53
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef struct _nod
{
	long int info;
	struct _nod *adr;
} nod;

typedef struct 
{
	struct _nod *cap;
} list;

list A[100001];
long int n;
long int m;
long int C[100001];
char viz[100001];
long int nr = 0;

void citire(void)
{
	long int a;
	long int b;
	FILE *f = fopen("dfs.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	for(long int i=1;i<=m;i++)
	{
		fscanf(f,"%ld %ld",&a,&b);
		nod *nou = (nod*)malloc(sizeof(nod));
		nou->info = b;
		nou->adr = A[a].cap;
		A[a].cap = nou;
		nod *nou1 = (nod*)malloc(sizeof(nod));
		nou1->info = a;
		nou1->adr = A[b].cap;
		A[b].cap = nou1;
	}
	
	fclose(f);
}

void parcurgere(int nod1)
{
	long int pi = 1;
	long int pf = 1;
	viz[nod1] = nr;
	C[1] = nod1;
	while(pi<=pf)
	{
		pi++;
		nod *q = A[C[pi-1]].cap;
		while(q)
		{
			if(viz[q->info] < 1)
			{
				C[++pf] = q->info;
				viz[q->info] = nr;
			}
			q = q->adr;
		}
	}
}

void adaugare(void)
{

	for(int i=1;i<=n;i++)
		if(viz[i]<1)
		{
			nr ++;
			parcurgere(i);
		}
}

int main()
{
	FILE *f = fopen("dfs.out","w");
	
	citire();
	adaugare();
	fprintf(f,"%d",nr);
	return 0;
	
	fclose(f);
}