Pagini recente » Cod sursa (job #320350) | Cod sursa (job #2701268) | Cod sursa (job #2117214) | Cod sursa (job #1559551) | Cod sursa (job #3139709)
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
int components;
int nr_nodes, nr_edges;
int node1, node2;
vector<vector<int>> graph;
bitset<100002> is_node_visited;
void dfs(int node) {
is_node_visited[node] = true;
for(auto next_node: graph[node]) {
if(!is_node_visited[next_node]) {
dfs(next_node);
}
}
}
int main()
{
ifstream fin("dfs.in");
fin >> nr_nodes >> nr_edges;
graph.resize(nr_nodes + 1);
for(int i = 0; i < nr_edges; i++) {
fin >> node1 >> node2;
graph[node1].push_back(node2);
graph[node2].push_back(node1);
}
fin.close();
for(int node = 1; node <= nr_nodes; node++) {
if(!is_node_visited[node]) {
dfs(node);
components ++;
}
}
ofstream fout("dfs.out");
fout << components << endl;
fout.close();
return 0;
}