Cod sursa(job #2831170)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 10 ianuarie 2022 21:45:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
using ll = long long;

const string fn = "dfs";


ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int ans;
int n, m;

bitset<100005> viz;
vector<int> g[100005];


void dfs(int nod) {

    viz[nod] = true;
    for (int son : g[nod]) {
        if (!viz[son])
            dfs(son);
    }

}

int main() {

    int x, y;

    fin >> n >> m;

    while (m--) {
        fin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

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

    fout << ans << '\n';

    fin.close();
    fout.close();
    return 0;
}