Cod sursa(job #2644172)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 23 august 2020 17:26:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> &arcs, vector<int> &visited, int currentNode, int compNo) {
	visited[currentNode] = compNo;

	for(int i=0; i<arcs[currentNode].size(); ++i)
		if ( ! visited[arcs[currentNode][i]]){
			dfs(arcs, visited, arcs[currentNode][i], compNo);
		}
}


int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

	int n, m, compNo, x, y;
	scanf("%d%d", &n, &m);
	vector<vector<int>> arcs(n+1);
	vector<int> visited(n+1);

	for(int i=0; i<m; ++i) {
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
		arcs[y].push_back(x);
	}

	compNo = 0;
	for(int i=1; i<=n; ++i)
		if (visited[i] == 0) {
			++compNo;
			dfs(arcs, visited, i, compNo);
		}

	printf("%d\n", compNo);
	return 0;
}