Pagini recente » Cod sursa (job #1924051) | Cod sursa (job #1997960) | Cod sursa (job #1235442)
#include <fstream>
#include <list>
#include <vector>
#include <stack>
void dfs(int node_nr,
const std::vector< std::list<int> > &graph,
std::vector<bool> &visited)
{
visited[node_nr] = true;
for (auto &i : graph[node_nr])
if (!visited[i])
dfs(i, graph, visited);
}
void dfs_iter(int node_nr,
const std::vector< std::list<int> > &graph,
std::vector<bool> &visited)
{
std::stack<int> nodes;
nodes.push(node_nr);
while (!nodes.empty()) {
int node = nodes.top();
nodes.pop();
if (!visited[node]) {
visited[node] = true;
for (auto &i : graph[node])
nodes.push(i);
}
}
}
int main()
{
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
int N, M;
in >> N >> M;
std::vector< std::list<int> > graph(N+1);
for (int i = 0; i < M; ++i) {
int x, y;
in >> x >> y;
graph[x].push_front(y);
graph[y].push_front(x);
}
std::vector<bool> visited_nodes(N+1, false);
int count = 0;
for (int i = 1; i <= N; ++i)
if (!visited_nodes[i]) {
++count;
dfs_iter(i, graph, visited_nodes);
}
out << count;
in.close();
out.close();
return 0;
}