Pagini recente » Cod sursa (job #2234245) | Cod sursa (job #99150) | Cod sursa (job #2151841) | Cod sursa (job #616006) | Cod sursa (job #1791073)
#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())
{
active.pop();
for (vector<int>::iterator it = neighbours[index].begin(); it != neighbours[index].end(); ++it)
if (!marked[*it])
active.push(*it), marked[*it] = 1;
}
}
cout << k;
return 0;
}