Cod sursa(job #2758827)

Utilizator speed2kkBoca Vlad Gabriel speed2kk Data 13 iunie 2021 10:53:50
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }


template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

ifstream f("dfs.in");
ofstream g("dfs.out");

const int NAX = 100000;

int N, M;
vector<int> adj[NAX];
bool visited[NAX];

void dfs(int s) {
    if (visited[s])
        return;

    visited[s] = true;

    for (auto u : adj[s])
        dfs(u);
}

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    f >> N >> M;

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

    f.close();

    int insule = 0;

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            insule++;
            dfs(i);
        }
    }

    g << insule;

    return 0;
}