Cod sursa(job #3157797)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 16 octombrie 2023 21:26:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
//ALEXANDRU MICLEA

// #include <vector>
// #include <algorithm>
// #include <string>
// #include <cstring>
// #include <queue>
// #include <map>
// #include <set>
// #include <unordered_set>
// #include <unordered_map>
// #include <time.h>
// #include <iomanip>
// #include <deque>
// #include <math.h>
// #include <cmath>
// #include <assert.h>
// #include <stack>
// #include <bitset>
// #include <random>
// #include <chrono>
// #include <iostream>
// #include <fstream>
// #include <array>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//VARIABLES

int n, m, cc;
vector <int> v[100005];
int visited[100005];

//FUNCTIONS

void dfs(int nod) {
    
    visited[nod] = 1;

    for (auto& x : v[nod]){
        if (!visited[x]){
            dfs(x);
        }
    }
}

//MAIN
int main() {

#ifdef INFOARENA
    ifstream fin("dfs.in"); ofstream fout("dfs.out");
    cin.rdbuf(fin.rdbuf()); cout.rdbuf(fout.rdbuf());
#endif

    //cout << "Hello world!\n";

    cin >> n >> m;
    while (m--) {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for (int i = 1; i <= n; i++){
        if (!visited[i]) cc++, dfs(i);
    }

    cout << cc << '\n';

    return 0;
}