Pagini recente » Cod sursa (job #520648) | Cod sursa (job #3301948) | Cod sursa (job #3301946) | Cod sursa (job #3318409) | Cod sursa (job #3318403)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
void DFS(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, adj, visited);
}
}
}
void solve() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int X, Y;
fin >> X >> Y;
adj[X].push_back(Y);
adj[Y].push_back(X);
}
vector<bool> visited(N + 1, false);
int component_count = 0;
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
component_count++;
DFS(i, adj, visited);
}
}
fout << component_count << endl;
fin.close();
fout.close();
}
int main() {
solve();
return 0;
}