Pagini recente » Borderou de evaluare (job #1594606) | Cod sursa (job #3329057) | Diferente pentru aib intre reviziile 26 si 22 | Cod sursa (job #320314) | Cod sursa (job #3333641)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream input ("dfs.in");
std::ofstream output ("dfs.out");
int main () {
int n, m;
input >> n >> m;
std::vector<std::vector<int>> graph(n + 1);
for (int i = 0; i < m; ++i) {
int x, y;
input >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
std::vector<bool> visited(n + 1, false);
int componentCount = 0;
for (int i = 1; i <= n; i++) {
int currentComponentSize = 0;
if (!visited[i]) {
//output << "DFS started from node " << i << "\n";
componentCount++;
std::stack<int> stack;
stack.push(i);
visited[i] = true;
while (!stack.empty()) {
int currentNode = stack.top();
stack.pop();
currentComponentSize++;
//output << currentNode << " ";
for (int neighborNode : graph[currentNode]) {
if (!visited[neighborNode]) {
visited[neighborNode] = true;
stack.push(neighborNode);
}
}
}
//output << "\n";
}
}
output << componentCount;
return 0;
}