Cod sursa(job #2243768)

Utilizator dinugaftonGafton Dinu dinugafton Data 21 septembrie 2018 12:38:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,k,s;
vector <int> v[100010];
queue <int> q;
bool viz[100010];
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()
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	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;
}