Cod sursa(job #2382417)

Utilizator stewie368Stefan stewie368 Data 18 martie 2019 11:59:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,k;

ifstream fin("dfs.in");
ofstream fout("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(){
	fin>>n>>m;
	for (int i=1;i<=m;i++){
		fin>>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++;
		}
	}
	fout<<k;
	return 0;
}