Cod sursa(job #1437572)

Utilizator maricasorinSorin-Gabriel maricasorin Data 17 mai 2015 22:49:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    ifstream f("dfs.in");
    int nr=0,y,n,m,a,b;
    f>>n>>m;
    vector <int> vecini[n+1],viz;
    stack <int> p;
    for (int i=0;i<m;i++)
    {
        f>>a>>b;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
    viz.resize(n+1);
    for (int i=1;i<=n;i++) viz[i]=0;
    for (int j=1;j<=n;j++)
        if (viz[j]==0)
        {
        p.push(j);
        while (!p.empty())
            {
            y=p.top();
            p.pop();
            if (viz[y]==0)
                {
                viz[y]=1;
                for (int i=vecini[y].size()-1;i>=0;i--) p.push(vecini[y][i]); //parcurgere de la dreapta la stanga pentru ca varful stivei sa fie ales cel mai mic nod ca si valoare
                }
            }
        nr++;
        }
    ofstream g("dfs.out");
    g<<nr;
    return 0;
}