Cod sursa(job #2406100)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 15 aprilie 2019 13:01:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 100000

using namespace std;

int  n,m ;

vector < vector<int> > v1(Nmax);

vector< bool > viz(Nmax,false);

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

    in>>n>>m ;

    int x, y;

    for(int i = 0 ; i <  m ; i ++)
    {
        in>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);

    }
}

void dfs(int x)
{
    viz[x] = true;



    for(int i = 0 ; i <  v1[x].size() ; i ++ )
           if(!viz[v1[x][i]])
               dfs(v1[x][i]);

}

int main()
{

    citire();

    int nrc =0 ;

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

        ofstream out("dfs.out");
        out<<nrc;



    return 0;
}