Pagini recente » Cod sursa (job #1329576) | Cod sursa (job #2546261) | Cod sursa (job #2744792) | Cod sursa (job #2570123) | Cod sursa (job #3295228)
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void dfsRec(vector<vector<int>> &adj, vector<bool> &visited, int s) {
visited[s] = true;
// vizitez recursiv toate muschiile adiacente
for (int x : adj[s]) {
if (visited[x] == false) {
dfsRec(adj, visited, x);
}
}
}
int dfs(vector<vector<int>> &adj) {
vector<bool> visited(adj.size(), false);
int cnt = 0;
for(int i = 1; i < adj.size(); i++) {
if (!visited[i]) {
cnt++;
dfsRec(adj, visited, i);
}
}
return cnt;
}
int main() {
// determinati numarul componentelor conexe ale grafului neorientat
// parcurgeri dfs noduri nemarcate si marcarea lor in aceste parcurgeri
// N nr noduri, M nr muchii
// lista cu muchiile
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int N, M, a, b;
cin >> N >> M;
vector<vector<int>> adj(N + 1);
for (int i = 1; i <= M; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int res = dfs(adj);
cout << res;
return 0;
}