Cod sursa(job #2668427)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 4 noiembrie 2020 21:45:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

void dfs(vector<list<int>>& graph, vector<bool>& visited, int start) {
	stack<int> st;
	st.push(start);

	while (st.size() > 0) {
		int node = st.top();
		st.pop();

		for (int i : graph[node]) {
			if (!visited[i]) {
				st.push(i);
				visited[i] = true;
			}
		}
	}
}

int main()
{
	ifstream fi("dfs.in");
	ofstream fo("dfs.out");

	int m, n;
	
	fi >> n >> m;
	vector<list<int>> graph(n);
	
	for (int i = 0; i < m; i++) {
		int a, b;
		fi >> a >> b;
		a--;
		b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	vector<bool> visited(n, false);
	stack<int> st;
	int count = 0;

	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			dfs(graph, visited, i);
			count++;
		}
	}

	fo << count;

	fi.close();
	fo.close();
	return 0;
}