Cod sursa(job #472850)

Utilizator robigiirimias robert robigi Data 26 iulie 2010 20:08:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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 add(int dest, int x)
{
	nod *p=new nod;
	p->x=x;
	p->adr=l[dest];
	l[dest]=p;
}


void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
}


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


void program()
{
	for (int i=1; i<=n; ++i)
	{	
		if (!viz[i])
		{
			nr++;
			dfs(i);
		}
	}

	fprintf(g, "%d", nr);
}




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