Cod sursa(job #1903301)

Utilizator derz223Adam Alexandru derz223 Data 5 martie 2017 09:29:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");


int x, y;
int n, m, i, counter, start;

stack<int> vecini;

int main()
{

    f>>n>>m;

    vector<list<int> >noduri(n+1);
    vector<bool> vizitat(n+1);

    for(i=1; i<=n; i++)
        vizitat[i] = false;
    for(i=1; i<=m; i++){
        f>>x>>y;
        noduri[x].push_back(y);
        noduri[y].push_back(x);
    }

    for(i=1; i<=n; i++){

        if(vizitat[i] == false){

            counter++;

            vecini.push(i);
            vizitat[i] = true;

            while(!vecini.empty()){

                    int aux = vecini.top();
                    vecini.pop();


                    for(int tmp : noduri[aux]){
                        if(vizitat[tmp]==false){
                            vizitat[tmp] = true;
                            vecini.push(tmp);
                        }
        }

        }

    }


    }


    g<<counter;

    return 0;

}