Pagini recente » Cod sursa (job #2575686) | Cod sursa (job #2731330) | Cod sursa (job #546726) | Cod sursa (job #3285774) | Cod sursa (job #2820529)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
bitset<100001> is_visited;
vector<int> neighbors[100001]; // if there is value y on position x => there is a vertice between x and y
void dfs_traversal(int node) {
is_visited[node] = true;
int current_nr_neighbors = neighbors[node].size();
for (int i = 0; i < current_nr_neighbors; ++i) {
if (!is_visited[neighbors[node][i]]) {
dfs_traversal(neighbors[node][i]);
}
}
}
int main() {
int nr_nodes, nr_vertices;
fin >> nr_nodes >> nr_vertices;
int node_1, node_2;
for (int vertex = 1; vertex <= nr_vertices; ++vertex) {
fin >> node_1 >> node_2;
neighbors[node_1].push_back(node_2);
neighbors[node_2].push_back(node_1);
}
int cnt_connected_components = 0;
for (int node = 1; node <= nr_nodes; ++node) {
if (!is_visited[node]) {
++cnt_connected_components;
dfs_traversal(node);
}
}
fout << cnt_connected_components;
return 0;
}