Cod sursa(job #2426039)

Utilizator ciprian.perju.fmiCiprian Perju ciprian.perju.fmi Data 25 mai 2019 20:19:06
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
//#include "pch.h"
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
int n, m, x, y, k;

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

vector <int> v[100010];
bool viz[100010];
queue <int> q;

void bfs(int start)
{
	q.push(start);
	viz[start] = 1;
	while (!q.empty())
	{
		int nod = q.front();
		q.pop();
		for (int i = 0; i < v[nod].size(); i++)
		{
			if (!viz[v[nod][i]]) q.push(v[nod][i]), viz[v[nod][i]] = 1;
		}
	}
}

int main() 
{
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!viz[i]) {
			bfs(i);
			k++;
		}
	}
	out << k;
	return 0;
}