Cod sursa(job #2654785)

Utilizator StefanSanStanescu Stefan StefanSan Data 2 octombrie 2020 11:56:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>
#include      <queue>
#include      <vector>
#include      <stack>

using namespace std;

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

int n, m, nr = 0;
bool vizitat[100001];
vector < int > V[100001];

void dfs(int nodStart) {
	stack < int > st;
	st.push(nodStart);
	while (!st.empty()) {
		int nodCurent = st.top();
		st.pop();

		for (int i = 0; i < V[nodCurent].size(); i++) {
			if (!vizitat[V[nodCurent][i]]) {
				vizitat[V[nodCurent][i]] = true;
				st.push(V[nodCurent][i]);
			}
		}

	}
}

int main() {
	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		in >> x >> y;
		V[x].push_back(y);
		V[y].push_back(x);
	}

	for (int i = 1; i <= n; i++) {
		if (!vizitat[i]) {
			dfs(i);
			nr++;
		}
	}

	out << nr;

	return 0;
	 
}