Mai intai trebuie sa te autentifici.

Cod sursa(job #2467722)

Utilizator MescareidMescareid Mescareid Data 4 octombrie 2019 21:59:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

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

int N, M;

vector<int> g[100005];
bool viz[100005];
int ncc;

void citire()
{
	in >> N >> M;
	int x, y;

	for (int i{ 0 }; i < M; ++i) {
		in >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

}

void DFS(int node)
{
	for(auto& i : g[node])
		if (!viz[i]) {
			viz[i] = true;
			DFS(i);
		}
}

void solve()
{
	for(int i{ 1 }; i <= N; ++i)
		if (!viz[i]) {
			DFS(i);
			++ncc;
		}

	out << ncc;
}

int main()
{
	citire();
	solve();
}