Cod sursa(job #483162)

Utilizator petroMilut Petronela petro Data 7 septembrie 2010 09:45:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
#include<vector>
#define M 100003
#define pb push_back
using namespace std;

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

long n,m,viz[M];
vector<long> a[M];

void cit()
{
	f>>n>>m;
	long i,x,y;
	
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
	}
	f.close();
}

void dfs(long x, long nr)
{
	long i;
	viz[x]=1;
	for(i=0;i<a[x].size();++i)
		if(viz[a[x][i]]==0) dfs(a[x][i],nr);
}

int main()
{
	cit();
	long nr=0,i;
	
	for(i=1;i<=n;++i)
		if(viz[i]==0) {++nr; dfs(i,nr);}
	
	g<<nr<<"\n";
	g.close();
	return 0;
}