Pagini recente » Cod sursa (job #942327) | Cod sursa (job #2811985) | Cod sursa (job #1055625) | Cod sursa (job #1166075) | Cod sursa (job #3224354)
#include <iostream>
#include <vector>
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;
}
int main() {
int n, m;
ifstream inputFile("dfs.in");
ofstream outputFile("dfs.out");
int n;
inputFile >> n;
int m;
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;
}