Cod sursa(job #2925748)

Utilizator RaduAntoneoAntonio Alexandru Radu RaduAntoneo Data 15 octombrie 2022 23:35:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
using namespace std;

void DFS(int currNode, vector<vector<int>> &adj, vector<bool> &vizited) {
	vizited[currNode] = 1;

	for (int x : adj[currNode])
		if (!vizited[x])
			DFS(x, adj, vizited);
}

ifstream f("dfs.in");
ofstream g("dfs.out");
#define cin f
#define cout g

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n+1);
	vector<bool> vizited(n+1, 0);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int count = 0;
	for (int i = 1; i <= n; i++)
		if (!vizited[i]) {
			count++;
			DFS(i, adj, vizited);
		}

	cout << count;
	return 0;
}