Cod sursa(job #535687)

Utilizator dianadobrescuDobrescu Diana dianadobrescu Data 17 februarie 2011 17:07:48
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream.h>
#define NMAX 10010

ifstream f("dfs.in");
ofstream g("dfs.out");

int p[NMAX], fr[NMAX], n, m, nr=0;

void Initializeaza()
{
	int i;
	for (i=1; i<=n; ++i) p[i]=i;
}

void Unifica(int x, int y)
{
	int i;
	if (p[x]!=p[y])
	{
		for (i=1; i<=n; ++i)
			if (i!=y && p[i]==p[y]) p[i]=p[x];
		p[y]=p[x];
	}
}

void Citeste()
{
	int x, y, i;
	f>>n>>m;
	Initializeaza();
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		Unifica(x, y);
	}
}

void Solve()
{
	int i;
	for (i=1; i<=n; ++i) fr[p[i]]=1;
	for (i=1; i<=n; ++i) nr+=fr[i];
}

void Afiseaza()
{
	g<<nr<<"\n";
}

int main()
{
	
	Citeste();
	
	Solve();
	
	Afiseaza();
	
	f.close();
	g.close();
	return 0;
}