Pagini recente » Cod sursa (job #1600244) | Cod sursa (job #2588235) | ONIS 2014, Runda 2 | Cod sursa (job #454514) | Cod sursa (job #1791074)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
int main()
{
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int nodes, edges;
cin >> nodes >> edges;
vector<int> neighbours[nodes];
int index;
int node1, node2;
for (index = 0; index < edges; ++index)
{
cin >> node1 >> node2;
neighbours[node1-1].push_back(node2-1);
neighbours[node2-1].push_back(node1-1);
}
vector<int> marked(nodes);
marked.resize(nodes);
for (index = 0; index < nodes; ++index)
marked[index] = 0;
int k = 0;
stack<int> active;
for (index = 0; index < nodes; ++index)
if(marked[index] == 0)
{
active.push(index);
marked[index] = 1;
++k;
while (!active.empty())
{
int current_value = active.top();
active.pop();
for (vector<int>::iterator it = neighbours[current_value].begin(); it != neighbours[current_value].end(); ++it)
if (!marked[*it])
{
active.push(*it);
marked[*it] = 1;
}
}
}
cout << k;
return 0;
}