Cod sursa(job #2140426)

Utilizator shantih1Alex S Hill shantih1 Data 23 februarie 2018 14:40:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int rz,m,n,i,j,a,b;
bool viz[100005];
vector<int> veci[100005];
deque<int> co;

int main () {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		veci[a].push_back(b);
		veci[b].push_back(a);
	}
	for(j=1;j<=n;j++)
		if(viz[j]==0)
		{
			rz++;
			co.push_back(j);
			viz[j]=1;
			while(!co.empty())
			{
				a=co.front();
				co.pop_front();
				for(i=0;i<veci[a].size();i++)
				{
					if(viz[veci[a][i]]==0)
					{
						viz[veci[a][i]]=1;
						co.push_back(veci[a][i]);
					}
				}
			}
		}
	fout<<rz<<"\n";
}