Pagini recente » Cod sursa (job #628001) | Cod sursa (job #109057) | Cod sursa (job #3128024) | Cod sursa (job #2612113) | Cod sursa (job #779229)
Cod sursa(job #779229)
#include <fstream>
#include <vector>
#include <list>
#include <utility>
#include <stack>
typedef std::list<unsigned int> edge;
typedef std::vector<edge> graph;
unsigned int DepthFirstSearch (graph &g)
{
std::stack<unsigned int> stack;
edge::const_iterator iterator, stop;
std::vector<bool> visited(g.size(),false);
unsigned int components(0), neighbor;
for (unsigned int node(1), end(visited.size()) ; node < end ; ++node)
{
if (!visited[node])
{
stack.push(node);
visited[node] = true;
do
{
neighbor = stack.top();
stack.pop();
for (iterator = g[neighbor].begin(), stop = g[neighbor].end() ; iterator != stop ; ++iterator)
if (!visited[*iterator])
{
stack.push(*iterator);
visited[*iterator] = true;
}
}
while (!stack.empty());
++components;
}
}
return components;
}
int main (void)
{
unsigned int n,m;
std::ifstream input("dfs.in");
input >> n >> m;
unsigned int node1, node2;
graph g(n + 1);
while (m)
{
input >> node1 >> node2;
g[node1].push_front(node2);
g[node2].push_front(node1);
--m;
}
input.close();
unsigned int components(DepthFirstSearch(g));
std::ofstream output("dfs.out");
output << components << '\n';
output.close();
return 0;
}