Cod sursa(job #2489214)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 8 noiembrie 2019 08:59:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector <int> graf[100003];queue <int> chestie;
int n,m,kontor,vizitat[100003],nod;
void bfs () {
	vizitat[chestie.front()]=1;
	while(chestie.size()!=0) {
		nod=chestie.front();
		for(int i=0;i<(int)graf[nod].size();++i)
			if(vizitat[graf[nod][i]]==0)
				vizitat[graf[nod][i]]=1,chestie.push(graf[nod][i]);
		chestie.pop();
	}
}
int main () {
	int nr1,nr2;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(int i=1;i<=m;++i)
		scanf("%d%d", &nr1, &nr2),graf[nr1].push_back(nr2),graf[nr2].push_back(nr1);
	for(int i=1;i<=n;++i)
		if(vizitat[i]==0) {
			++kontor;chestie.push(i);
			bfs();
		}
	printf("%d", kontor);
	return 0;
}