Cod sursa(job #3319327)

Utilizator EckchartZgarcea Robert-Andrei Eckchart Data 31 octombrie 2025 17:55:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
// #define LOCAL
#ifdef LOCAL
ifstream cin("input.txt");
ofstream cout("output2.txt");
#else
ifstream cin("dfs.in");
ofstream cout("dfs.out");
#endif
#define cin ::cin
#define cout ::cout


int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1);
    while (M--)
    {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    set<int> visited_nodes;

    auto dfs = [&](auto &self, const int node) -> void
    {
        visited_nodes.emplace(node);
        for (const int anode : adj[node])
        {
            if (visited_nodes.count(anode))
            {
                continue;
            }
            self(self, anode);
        }
    };

    int nr_ccs = 0;
    for (int node = 1; node <= N; ++node)
    {
        if (visited_nodes.count(node))
        {
            continue;
        }
        dfs(dfs, node);
        ++nr_ccs;
    }

    cout << nr_ccs;
}