Cod sursa(job #2890024)

Utilizator mihnea.tTudor Mihnea mihnea.t Data 14 aprilie 2022 09:47:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

#define NMAX ((int)1e5 + 2)

using namespace std;

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

int n, m;
vector<int> adj[NMAX];

void dfs(int node, vector<bool> &viz) {
    for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
        int next = *it;
        if (!viz[next]) {
            viz[next] = true;
            dfs(next, viz);
        }
    }
}

int main(void) {
    fin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    int cnt = 0;
    vector<bool> viz(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            dfs(i, viz);
            ++cnt;
        }
    }

    fout << cnt << "\n";

    return 0;
}