Cod sursa(job #1169258)

Utilizator OlaruSabinOlaru Sabin OlaruSabin Data 10 aprilie 2014 19:55:06
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int>v[100005];
int conexe,viz[100005],noduri,muchii,nod1,nod2,i,n;
int dfs(int nod)
{
	for(int k=0;k<=v[nod].size()-1;k++)
	{
		if(!viz[v[nod][k]])
		{
			viz[v[nod][k]]=1;
			dfs(v[nod][k]);
		}
	}
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&noduri,&muchii);
	for(i=1;i<=muchii;i++)
	{
		scanf("%d%d",&nod1,&nod2);
		v[nod1].push_back(nod2);
		v[nod2].push_back(nod1);
	}
	for(i=1;i<=noduri;i++)
	{
		if(!viz[i])
		{
			viz[i]=1;
			conexe++;
			if(v[i].size())
			dfs(i);
		}
	}
	printf("%d",conexe);
}