Pagini recente » Cod sursa (job #1463601) | Cod sursa (job #2192937) | Cod sursa (job #795459) | Cod sursa (job #1608407) | Cod sursa (job #1527310)
#include <stack>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
int main() {
ifstream f{"dfs.in"};
ofstream g{"dfs.out"};
int n, m;
f >> n >> m;
vector<vector<int>> edges(n);
for (int i = 0; i < m; i++) {
int s, d;
f >> s >> d;
s--; d--;
edges[s].push_back(d);
edges[d].push_back(s);
}
vector<int> seen(n, 0);
int i = 0;
int seen_nodes = 0;
int comps = 0;
while (seen_nodes < n) {
//std::cout << " i = " << i << std::endl;
while (i < seen.size() && seen[i] == 1)
i++;
if (i == seen.size())
break;
// i is source
stack<int> fringe;
fringe.push(i);
while (!fringe.empty()) {
int next = fringe.top();
//std::cout << " next = " << next << std::endl;
fringe.pop();
if (seen[next])
continue;
seen[next] = 1;
seen_nodes++;
//std::cout << " process = " << next << std::endl;
for (auto e : edges[next]) {
if (!seen[e]) {
fringe.push(e);
}
}
}
comps++;
}
g << comps << endl;
return 0;
}