Cod sursa(job #2809325)

Utilizator SmitOanea Smit Andrei Smit Data 26 noiembrie 2021 17:51:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int>L[100001];
bitset<100001>viz;

void DFS(int x)//primesc ca parametru un nod din graf
{
    unsigned int i;
    int y;
    viz[x] = 1;
    for(i=0;i<L[x].size();++i)//parcurg lista de vecini ai lui x
    {
         y = L[x][i];//y este vecin cu x
        if(viz[y]==0)//y nu a fost marcat inca
            DFS(y);//apelez DFS ca sa il marchez, si marchez si vecinii lui
    }
}

int main()
{
    int x, y;
    ifstream fin("dfs.in");
    fin>>N>>M;

    for(int i=1;i<=M;++i)
    {
        fin>>x>>y;
        L[x].push_back(y);//in lista de adiacenta (lista de vecini)
                          //il adaug pe y
        L[y].push_back(x);//adaug pe x la lista lui y
    }
    fin.close();
    //am terminat citirea

    //acum numaram componentele conexe
    int nr_comp_conexe = 0;
    for(int i=1;i<=N;++i)
        if(viz[i]==0)//am gasit un nod nevizitat
        {
            DFS(i);
            nr_comp_conexe++;
        }
    ofstream fout("dfs.out");
    fout<<nr_comp_conexe<<"\n";
    fout.close();

    return 0;
}