Cod sursa(job #2150191)

Utilizator danutmafteiMaftei Danut danutmaftei Data 3 martie 2018 12:38:48
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 100005

using namespace std;

int n,m;
int nrcomp;

vector<int>lista[Nmax];


bool viz[Nmax];

void citire()
{  ifstream fin("dfs.in");

    fin>>n>>m;

    int x,y;

    while(m--)
    {  fin>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(y);
    }

    fin.close();
}

void DFS(int nod)
{
    viz[nod]=true;

    for(size_t i=0;i<lista[nod].size();++i)
        if(!viz[lista[nod][i]])
            DFS(lista[nod][i]);

}
int main()
{
    citire();

    for(int i=1;i<=n;++i)
        if(!viz[i])
    {
        nrcomp++;
        DFS(i);
    }

    ofstream fout("dfs.out");
    fout<<nrcomp;
    return 0;
}