Cod sursa(job #2414558)

Utilizator E.L.Pnz Just E.L. Data 24 aprilie 2019 18:32:53
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void bfs(vector<vector<int>> &A,vector<bool> &Vizitat,unsigned poz)
{
	Vizitat[poz]=true;
	for(auto x : A[poz])
		if(Vizitat[x]==false)
			bfs(A,Vizitat,x);

}
int main()
{
	unsigned n,m,i,j;
	fin>>n>>m;
	vector<vector<int>> a (n+1);
	vector<bool> vizitat (n+1);
	for(i=0;i<m;i++)
	{
		unsigned x,y;
		fin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(i=1;i<=n;i++)
		vizitat[i]=false;


	unsigned long long K=0;

	for(i=1;i<=n;i++)
		if(vizitat[i]==false)
			{
				K++;
				bfs(a,vizitat,i);
			}

	fout<<K;
	return 0;

}