555E - Case of Computer Network - CodeForces Solution

#include "bits/stdc++.h"
#ifdef ON_PC
#include "debug.h"
#else
#define debug(x...)
#define debugV(x...)
#endif
using namespace std;
typedef long long ll;

struct UnionFind {
    int _n;
    vector<int> _par, _cnt;
    // 初始化 [0, n - 1]
    UnionFind() {}
    UnionFind(int n) : _n(n) {
        _par.resize(_n);
        _cnt.resize(_n, 1);
        for (int i = 0; i < _n; i++) _par[i] = i;
    }
    int root(int x) {
        if (_par[x] == x) return x;
        return _par[x] = root(_par[x]);
    }
    inline bool same(int x, int y) { return root(x) == root(y); }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (_cnt[y] < _cnt[x]) std::swap(x, y);
        _par[x] = y;
        _cnt[y] += _cnt[x];
        _cnt[x] = 0;
    }
    inline int cnt(int x) { return _cnt[root(x)]; }
};

template <typename T>
class graph {
   public:
    struct edge {
        int from;
        int to;
        T cost;
    };

    vector<edge> edges;
    vector<vector<int>> g;
    int n;

    graph(int _n) : n(_n) { g.resize(n); }

    virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class undigraph : public graph<T> {
   public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;
    undigraph(int _n) : graph<T>(_n) {}
    int add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int id = (int)edges.size();
        g[from].push_back(id);
        g[to].push_back(id);
        edges.push_back({from, to, cost});
        return id;
    }
};

template <typename T>
class undigraph_dfs_forest : public undigraph<T> {
   public:
    using undigraph<T>::edges;
    using undigraph<T>::g;
    using undigraph<T>::n;

    vector<int> depth;
    unordered_set<int> bridges;  // edge ids
    vector<int> across_span_edge_cnt;
    vector<bool> vis;

    // 1:from->to  0:to->from
    // parent->children , children->ancestor
    vector<bool> direction;  // <edge_id, bool>

    undigraph_dfs_forest(int _n) : undigraph<T>(_n) {}

    void init() {
        depth = vector<int>(n, -1);
        across_span_edge_cnt = vector<int>(n, 0);
        direction = vector<bool>(edges.size(), 0);
        vis = vector<bool>(edges.size(), 0);
    }

    void clear() {
        depth.clear();
        bridges.clear();
        across_span_edge_cnt.clear();
        direction.clear();
    }

   private:
    void do_dfs(int u, int fa) {
        for (int id : g[u]) {
            auto& e = edges[id];
            int v = e.from ^ e.to ^ u;
            if (vis[id]) {
                continue;
            }
            vis[id] = 1;
            if (depth[v] != -1) {
                if (depth[v] < depth[u]) {
                    across_span_edge_cnt[u]++;
                    across_span_edge_cnt[v]--;
                    direction[id] = (e.from == u);
                }
                continue;
            }
            direction[id] = (e.from == u);
            depth[v] = depth[u] + 1;
            do_dfs(v, u);
            across_span_edge_cnt[u] += across_span_edge_cnt[v];
            if (across_span_edge_cnt[v] == 0) {
                bridges.insert(id);
            }
        }
    }

    void do_dfs_from(int v) {
        depth[v] = 0;
        do_dfs(v, v);
    }

   public:
    void dfs(int v) {
        init();
        do_dfs_from(v);
    }

    void dfs_all() {
        init();
        for (int v = 0; v < n; v++) {
            if (depth[v] == -1) {
                do_dfs_from(v);
            }
        }
    }
};

template <typename T>
class forest : public graph<T> {
   public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;

    forest(int _n) : graph<T>(_n) {}

    int add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int id = (int)edges.size();
        assert(id < n - 1);
        g[from].push_back(id);
        g[to].push_back(id);
        edges.push_back({from, to, cost});
        return id;
    }
};

template <typename T>
class dfs_forest : public forest<T> {
   public:
    using forest<T>::edges;
    using forest<T>::g;
    using forest<T>::n;

    vector<int> pv;
    vector<int> pe;
    vector<int> order;
    vector<int> pos;
    vector<int> end;
    vector<int> sz;
    vector<int> root;
    vector<int> depth;
    vector<T> dist;

    dfs_forest(int _n) : forest<T>(_n) {}

    void init() {
        pv = vector<int>(n, -1);
        pe = vector<int>(n, -1);
        order.clear();
        pos = vector<int>(n, -1);
        end = vector<int>(n, -1);
        sz = vector<int>(n, 0);
        root = vector<int>(n, -1);
        depth = vector<int>(n, -1);
        dist = vector<T>(n);
    }

    void clear() {
        pv.clear();
        pe.clear();
        order.clear();
        pos.clear();
        end.clear();
        sz.clear();
        root.clear();
        depth.clear();
        dist.clear();
    }

   private:
    void do_dfs(int v) {
        pos[v] = (int)order.size();
        order.push_back(v);
        sz[v] = 1;
        for (int id : g[v]) {
            if (id == pe[v]) {
                continue;
            }
            auto& e = edges[id];
            int to = e.from ^ e.to ^ v;
            depth[to] = depth[v] + 1;
            dist[to] = dist[v] + e.cost;
            pv[to] = v;
            pe[to] = id;
            root[to] = (root[v] != -1 ? root[v] : to);
            do_dfs(to);
            sz[v] += sz[to];
        }
        end[v] = (int)order.size() - 1;
    }

    void do_dfs_from(int v) {
        depth[v] = 0;
        dist[v] = T{};
        root[v] = v;
        pv[v] = pe[v] = -1;
        do_dfs(v);
    }

   public:
    void dfs(int v, bool clear_order = true) {
        if (pv.empty()) {
            init();
        } else {
            if (clear_order) {
                order.clear();
            }
        }
        do_dfs_from(v);
    }

    void dfs_all() {
        init();
        for (int v = 0; v < n; v++) {
            if (depth[v] == -1) {
                do_dfs_from(v);
            }
        }
        assert((int)order.size() == n);
    }
};

template <typename T>
class lca_forest : public dfs_forest<T> {
   public:
    using dfs_forest<T>::edges;
    using dfs_forest<T>::g;
    using dfs_forest<T>::n;
    using dfs_forest<T>::pv;
    using dfs_forest<T>::pos;
    using dfs_forest<T>::end;
    using dfs_forest<T>::depth;

    int h;
    vector<vector<int>> pr;

    lca_forest(int _n) : dfs_forest<T>(_n) {}

    inline void build_lca() {
        assert(!pv.empty());
        int max_depth = 0;
        for (int i = 0; i < n; i++) {
            max_depth = max(max_depth, depth[i]);
        }
        h = 1;
        while ((1 << h) <= max_depth) {
            h++;
        }
        pr.resize(n);
        for (int i = 0; i < n; i++) {
            pr[i].resize(h);
            pr[i][0] = pv[i];
        }
        for (int j = 1; j < h; j++) {
            for (int i = 0; i < n; i++) {
                pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);
            }
        }
    }

    inline bool anc(int x, int y) {
        return (pos[x] <= pos[y] && end[y] <= end[x]);
    }

    inline int go_up(int x, int up) {
        assert(!pr.empty());
        up = min(up, (1 << h) - 1);
        for (int j = h - 1; j >= 0; j--) {
            if (up & (1 << j)) {
                x = pr[x][j];
                if (x == -1) {
                    break;
                }
            }
        }
        return x;
    }

    inline int lca(int x, int y) {
        assert(!pr.empty());
        if (anc(x, y)) {
            return x;
        }
        if (anc(y, x)) {
            return y;
        }
        for (int j = h - 1; j >= 0; j--) {
            if (pr[x][j] != -1 && !anc(pr[x][j], y)) {
                x = pr[x][j];
            }
        }
        return pr[x][0];
    }
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    auto uf = UnionFind(n);
    auto g = undigraph_dfs_forest<int>(n);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        g.add(u, v);
    }
    g.dfs(0);
    for (int id = 0; id < g.edges.size(); id++) {
        int u = g.edges[id].from, v = g.edges[id].to;
        if (!g.bridges.count(id)) {
            uf.unite(u, v);
        }
    }
    // debugV(g.bridges);
    auto new_g = lca_forest<int>(n);
    for (int id = 0; id < g.edges.size(); id++) {
        int u = g.edges[id].from, v = g.edges[id].to;
        int pu = uf.root(u), pv = uf.root(v);
        if (pu == pv) continue;
        new_g.add(pu, pv);
        debugV(pu, pv);
    }
    new_g.dfs_all();
    new_g.build_lca();
    vector<int> lca_cnt(n, 0), s_cnt(n, 0), d_cnt(n, 0);
    int ok = 1;
    unordered_set<int> roots;
    for (int i = 0; i < q; i++) {
        int s, d;
        cin >> s >> d;
        s--;
        d--;
        int ps = uf.root(s), pd = uf.root(d);
        if (ps == pd) continue;
        if (new_g.root[ps] != new_g.root[pd]) {
            ok = 0;
            continue;
        }
        roots.insert(new_g.root[ps]);
        int lca = new_g.lca(ps, pd);
        lca_cnt[lca]++;
        s_cnt[ps]++;
        d_cnt[pd]++;
    }
    debugV(roots);
    if (ok) {
        function<void(int)> dfs;
        dfs = [&](int v) {
            for (int id : new_g.g[v]) {
                if (id == new_g.pe[v]) {
                    continue;
                }
                auto& e = new_g.edges[id];
                int to = e.from ^ e.to ^ v;
                dfs(to);
                lca_cnt[v] += lca_cnt[to];
                s_cnt[v] += s_cnt[to];
                d_cnt[v] += d_cnt[to];
            }
            if (!roots.count(v)) {
                debugV(v, lca_cnt[v], s_cnt[v], d_cnt[v]);
                if (s_cnt[v] > lca_cnt[v] and d_cnt[v] > lca_cnt[v]) ok = 0;
            }
        };
        for (int root : roots) dfs(root);
    }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}