Submission #3725120

---

Source Code Expand

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
struct edge { int i, u, v; };
template <bool Directed> struct graph {
    int n;
    vector<edge> edges;
    vector<vector<edge>> adj;
    graph(int n) : n(n), adj(n + 1) {}
    void add_edge(int u, int v) {
        int i = edges.size();
        edges.push_back({i, u, v});
        adj[u].push_back({i, u, v});
        if(not Directed) adj[v].push_back({i, v, u});
    }
};
template <bool Directed> int dfs(graph<Directed>& g,
const function<void(int, int)>& pre = [](int u, int from) {},
const function<void(int, int)>& pos = [](int u, int from) {}) {
    vector<bool> vis(g.n + 1);
    function<bool(int, int)> dfs = [&](int u, int from) {
        vis[u] = true;
        pre(u, from);
        bool tree = true;
        for(edge& e : g.adj[u]) {
            int u = e.u, v = e.v;
            if(not vis[v]) {
                tree &= dfs(v, u);
            } else if(v != from) {
                tree = false;
            }
        }
        pos(u, from);
        return tree;
    };
    int ans = 0;
    for(int u = 1; u <= g.n; u++) {
        if(not vis[u]) {
            ans += dfs(u, 0);
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph<0> g(n);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g.add_edge(u, v);
    }
    cout << dfs(g) << endl;
    return 0;
}

Submission Info

Judge Result