Cod sursa(job #1791072)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 29 octombrie 2016 01:52:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#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;
}