Pagini recente » Cod sursa (job #316557) | Cod sursa (job #1978706) | Cod sursa (job #2851101) | Cod sursa (job #3032229) | Cod sursa (job #3249457)
#include <fstream>
#include <iostream>
#include <vector>
void dfsHelper(const std::vector<std::vector<int>>& adjList, std::vector<bool>& visited, int s){
visited[s] = true;
for(const int& node : adjList[s]){
if(!visited[node])
dfsHelper(adjList, visited, node);
}
}
int dfs(){
std::ifstream in("dfs.in");
int n,m;
in >> n >> m;
std::vector<std::vector<int>> adjacencyList(n+1, std::vector<int>());
std::vector<bool> visited(n+1, false);
for(int i=0; i<m; i++){
int node1, node2;
in >> node1 >> node2;
adjacencyList[node1].push_back(node2);
adjacencyList[node2].push_back(node1);
}
in.close();
int conexCnt = 0;
for(int i=1; i<n+1; i++){
if(!visited[i]){
dfsHelper(adjacencyList, visited, i);
conexCnt++;
}
}
return conexCnt;
}
int main(){
std::ofstream out("dfs.out");
out << dfs();
return 0;
}