Cod sursa(job #2756569)

Utilizator laur0700Laurentiu Postole laur0700 Data 1 iunie 2021 14:23:25
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N, M, x, y, conexe;

bool b[100005];
vector <int>g[100005];

void Dfs(int nod)
{
    b[nod] = 1;

    for(auto i:g[nod])
    {
        if(b[i] == 0)
        {
            Dfs(i);
        }
    }
}

int main()
{
    fin>>N>>M;

    for(int i = 0; i<M; i++)
    {
        fin>>x>>y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 0; i<N; i++)
    {
        if(b[i] == 0)
        {
            Dfs(i);
            conexe++;
        }
    }

    fout<<conexe;

    return 0;
}