Cod sursa(job #733318)

Utilizator IliesiDanielDaniel IliesiDaniel Data 11 aprilie 2012 20:16:19
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long a[10000][10000],s[10000],N,M,nr,i;

void citire()
{
	int i,x,y;

	f>>N>>M;

	for(i=1;i<=M;i++)
	{
		f>>x>>y;
		a[x][y]=a[y][x]=1;
	}

	f.close();
}

void adancime(int vf)
{
	int u;

	s[vf]=1;

	for(u=1;u<=N;u++)
		if(a[vf][u]	&&	!s[u])
			adancime(u);
}

int main()
{
	citire();

	for(i=1;i<=N;i++)
		if(s[i]==0)
		{
			nr++;
			adancime(i);
		}

	g<<nr;

	g.close();
	return 0;
}