Cod sursa(job #2951451)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 6 decembrie 2022 12:37:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

const int MAX = 1e5 + 1;

int n , m , s , a , z , k;
vector <int> g[MAX];
bitset <MAX> b;

void dfs( int x ){

    int l = g[x].size();
    for(int i = 0 ; i < l ; i++){
        if(!b[g[x][i]]){

            b[g[x][i]] = 1;
            dfs(g[x][i]);
        }
    }
}

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

    while(m--){

        cin >> a >> z;
        g[a].push_back(z);
        g[z].push_back(a);
    }

    for(int i = 1 ; i <= n ; i++){

        if(!b[i]){

            dfs(i);
            k++;
        }

    }

    cout << k;

    return 0;
}