Pagini recente » Cod sursa (job #2554021) | Cod sursa (job #1353660) | Cod sursa (job #2515411) | Cod sursa (job #967308) | Cod sursa (job #2606327)
#include <bits/stdc++.h>
using namespace std;
const int kMod = 1e9 + 7;
class Node {
public:
int nr;
vector<Node*> neigh;
Node(int x) {
nr = x;
}
Node() {
nr = -1;
}
};
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<Node*> nodes;
void read_input() {
ifstream fin("dfs.in");
fin >> n >> m;
nodes.resize(n);
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
nodes[x]->nr = x;
nodes[y]->nr = y;
nodes[x]->neigh.push_back(nodes[y]);
nodes[y]->neigh.push_back(nodes[x]);
}
fin.close();
}
int get_result() {
int connected = 0;
vector<bool> visited(n);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(nodes[i], visited);
++connected;
}
}
return connected;
}
void dfs(Node* node, vector<bool> &visited) {
if (node->neigh.empty())
return;
visited[node->nr] = true;
for (auto it : node->neigh) {
if (!visited[it->nr])
dfs(it, visited);
}
}
void print_output(int result) {
ofstream fout("dfs.out");
fout << result << '\n';
fout.close();
}
};
// Please always keep this simple main function!
int main() {
// Allocate a Task object on heap in order to be able to
// declare huge static-allocated data structures inside the class.
Task *task = new Task();
task->solve();
delete task;
return 0;
}