Pagini recente » Cod sursa (job #3162303) | Cod sursa (job #1812455) | Cod sursa (job #2748320) | Cod sursa (job #1980620) | Cod sursa (job #3224363)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}
int countConnectedComponents(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, visited, graph);
count++;
}
}
return count;
}
ifstream inputFile("dfs.in");
ofstream outputFile("dfs.out");
int main() {
int n, m;
inputFile >> n;
inputFile >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int u, v;
inputFile >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int numComponents = countConnectedComponents(graph);
outputFile<< numComponents;
inputFile.close();
outputFile.close();
return 0;
}