Cod sursa(job #3308541)

Utilizator ViAlexVisan Alexandru ViAlex Data 25 august 2025 22:12:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include<iostream>
#include<fstream>
#include<deque>
#include<vector>
using namespace std;

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

int n, m;
vector<vector<int>> graph;
vector<int> visited;

void read() {
	in>>n>>m;
	graph.resize(n);
	visited.resize(n, false);

	int a, b;
	for (int i=0; i<m; i++){
		in>>a>>b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}
}

void dfs(int node) {
	visited[node] = true;
	for (int k: graph[node]) {
		if (!visited[k]) {
			dfs(k);
		}
	}
}

void solve() {
	int count = 0;
	for (int i=0; i < n;i++){
		if(!visited[i]) {
			dfs(i);
			count++;
		}
	}
	out<<count<<endl;
}


int main() {
	read();
	solve();
	return 0;
}