Cod sursa(job #2090537)

Utilizator marcogoldPop Mihali Marco Silviu marcogold Data 18 decembrie 2017 12:55:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <vector>
#include <fstream>
#define pb push_back

using namespace std;

ofstream fo("dfs.out");
ifstream fi("dfs.in");

int n,m,a,b,x;

vector <int> vecini[100001];

bool vazut[100001];

void neVazut()
{
    for(int i=1;i<=n;i++)
        vazut[i]=false;
}

void parcurgere(int nodCurent)
{
    vazut[nodCurent]=true;

    for( int i:vecini[nodCurent] )
    {
        if( !vazut[i] )
        {
            parcurgere(i);
        }
    }

}

int main()
{
    fi>>n>>m;

    for(int i=1;i<=m;i++)
    {
      fi>>a>>b;
      vecini[a].pb(b);
      vecini[b].pb(a);
    }

    neVazut();

    for(int i=1;i<=n;i++)
    {
        if(!vazut[i])
        {
            parcurgere(i);
            x++;
        }

    }

    fo<<x;

    return 0;
}