Cod sursa(job #2663946)

Utilizator paulaiugaPaula Iuga paulaiuga Data 27 octombrie 2020 17:27:41
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");


vector <int> adiacenta[100000];
bool vizitat[100000] = {false};

void DFS(int nod)
{
    vizitat[nod] = true;
    for(size_t i=0; i< adiacenta[nod].size(); i++)
    {
        if(!vizitat[adiacenta[nod][i]])
        {
            DFS(adiacenta[nod][i]);
        }
    }
//     for (auto it = adiacenta[nod].begin(); it != adiacenta[nod].end(); it++)
//     {
//         if(!vizitat[it])
//         {
//
//             DFS(it);
//         }
//
//     }
}
int main()
{
    int N,M,x,y;
    int nr_comp_conexe = 0;
    in>>N>>M;
    for(int i =1; i <=M ;i++)
    {
        in>>x>>y;
        adiacenta[x].push_back(y);
        //graf neorientat x y  muchie => x e vecinul lui y si y  e vecinul lui x
         adiacenta[y].push_back(x);

    }

     for(int i = 1; i <= N; i++)
    {
        if(!vizitat[i])
        {
            nr_comp_conexe += 1;
            DFS(i);
        }
    }

    out<<nr_comp_conexe<<"\n";




    return 0;
}