Cod sursa(job #472839)

Utilizator robigiirimias robert robigi Data 26 iulie 2010 19:43:57
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
// Parcurgere DFS - componente conexe.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("dfs.in", "r");
FILE *g=fopen("dfs.out", "w");

int n, m, nr;
int viz[100001];

typedef struct nod
{
	int x;
	struct nod *adr;
};

nod *l[100001];


void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		if (l[x]==NULL)
		{
			l[x]=new nod;
			l[x]->x=y;
			l[x]->adr=NULL;
		}
		else
		{
			nod *p=new nod;
			p->x=y;
			p->adr=l[x];
			l[x]=p;
		}
		if (l[y]==NULL)
		{
			l[y]=new nod;
			l[y]->x=x;
			l[y]->adr=NULL;
		}
		else
		{
			nod *q=new nod;
			q->x=x;
			q->adr=l[y];
			l[y]=q;
		}
	}
}


void dfs(int x)
{
	int cr=x;
	if (!viz[cr])
	{
		viz[0]++;
		viz[cr]=1;
		nod *p=l[cr];
		if (l[cr]==NULL) return;
		if (!viz[p->x])
			dfs(p->x);
		while (p->adr!=NULL)
		{
			if (!viz[p->adr->x])
				dfs(p->adr->x);
			p=p->adr;
		}
	}
}


void program()
{
	while (viz[0]!=n)
	{
		int i;
		for (i=1; i<=n && viz[i]; ++i);
		nr++;
		dfs(i);
	}
	fprintf(g, "%d", nr);
}




int main()
{
	read();
	program();
	return 0;
}