Pagini recente » Cod sursa (job #1487340) | Cod sursa (job #1229131) | Cod sursa (job #2192760) | Cod sursa (job #2893480) | Cod sursa (job #2196980)
#include <fstream>
#include <stack>
#include <vector>
#include <iostream>
int main() {
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
unsigned n, m;
in >> n >> m;
std::vector<std::vector<unsigned>> graph = std::vector<std::vector<unsigned>>();
graph.reserve(n);
for (unsigned i = 0; i < n; i++) graph.push_back(std::vector<unsigned>());
for (unsigned i = 0; i < m; i++) {
unsigned v1, v2;
in >> v1 >> v2;
graph[v1 - 1].push_back(v2);
graph[v2 - 1].push_back(v1);
}
unsigned numComponents = 0;
std::vector<bool> visited = std::vector<bool>();
visited.reserve(n);
for (unsigned i = 0; i < n; i++) visited.push_back(false);
unsigned numVisited = 0;
while (numVisited < n) {
unsigned first = 1;
for (unsigned i = 0; i < n; i++) {
if (!visited[i]) {
first = i + 1;
break;
}
}
std::stack<unsigned> s = std::stack<unsigned>();
s.push(first);
visited[first - 1] = true;
numVisited++;
while (!s.empty()) {
unsigned current = s.top();
bool hasNeighbors = false;
for (unsigned v : graph[current - 1]) {
if (!visited[v - 1]) {
hasNeighbors = true;
s.push(v);
visited[v - 1] = true;
numVisited++;
break;
}
}
if (!hasNeighbors) s.pop();
}
numComponents++;
}
out << numComponents;
return 0;
}