Cod sursa(job #2369811)

Utilizator LucaSeriSeritan Luca LucaSeri Data 6 martie 2019 09:20:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;


#ifdef HOME
    #define f cin
    #define g cout
#else
    ifstream f("dfs.in");
    ofstream g("dfs.out");
#endif // HOME

const int MAXN = 1e5 + 10;
vector< int > gr[MAXN];

bool viz[MAXN];

void dfs(int node) {
    viz[node] = true;
    for(auto &x : gr[node]) if(!viz[x]) dfs(x);
}
int main () {
    #ifdef HOME
        freopen("input", "r", stdin);
    #endif // HOME

    int n, m;
    f >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int a, b;
        f >> a >> b;

        gr[a].emplace_back(b);
        gr[b].emplace_back(a);
    }

        int ans = 0;
    for(int i = 1; i <= n; ++i) {
        if(!viz[i]) {
            ++ans;
            dfs(i);
        }
    }

    g << ans;
    return 0;
}