Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
4.2 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define nl '\n'
#define v vector

#ifdef WASSIM
#include "debug.h"
#else
#define dbg(...)
#endif

// O(V + E)
vector<int> comp, comps;
void tarjan(vector<vector<int>>& adj) {
    int n = adj.size(), curr = 0;
    comps.clear();
    comp.assign(n, -1);
    vector<int> disc(n), vis;

    auto dfs = [&](int u, auto&& dfs) -> int {
        int low = disc[u] = ++curr;
        vis.push_back(u);

        for (int& i : adj[u])
            if (comp[i] == -1)
                low = min(low, disc[i] ?: dfs(i, dfs));

        if (low == disc[u]) {
            comps.push_back(u);
            for (int i = -1; i != u;) {
                i = vis.back();
                comp[i] = u;
                vis.pop_back();
            }
        }
        return low;
    };

    for (int i = 0; i < n; i++)
        if (!disc[i]) dfs(i, dfs);
    reverse(comps.begin(), comps.end());
}

// O(V + E)
vector<int> topsort(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<char> vis(n);
    vector<int> order;

    auto dfs = [&](int u, auto&& dfs) -> void {
        vis[u] = 1;
        for (int& i : adj[u])
            if (not vis[i])
                dfs(i, dfs);
        order.push_back(u);
    };

    for (int i = 0; i < n; i++)
        if (not vis[i]) dfs(i, dfs);
    reverse(order.begin(), order.end());

    return order;
}

bool bruteforce(v<v<int>>& adj, v<array<int, 2>>& a) {
    int n = adj.size();

    v<int> cnt(n), vis(n);
    auto dfs = [&](int u, int end, auto&& dfs) -> bool {
        if (not vis[u]) cnt[u]++;
        vis[u] = 1;
        if (u == end) return 1;
        bool ok = 0;
        for (int& i : adj[u])
            ok |= dfs(i, end, dfs);
        if (not ok) cnt[u]--;
        return ok;
    };
    for (auto& [x, y] : a) {
        fill(vis.begin(), vis.end(), 0ll);
        dfs(x, y, dfs);
    }
    return count(cnt.begin(), cnt.end(), a.size()) > 0;
}

const int N = 5e4 + 1;

bool solve_dag(v<v<int>>& adj, v<array<int, 2>>& a) {
    int n = adj.size();

    v<bitset<N>> can_reach(n);
    v<int> vis(n);
    auto dfs = [&](int u, auto&& dfs) -> void {
        if (vis[u]) return;
        vis[u] = 1;
        can_reach[u][u] = 1;
        for (int& i : adj[u]) {
            dfs(i, dfs);
            can_reach[u] |= can_reach[i];
        }
    };
    for (int i = 0; i < n; i++)
        dfs(i, dfs);

    bool reach_check = 1;
    bitset<N> middle, end;
    middle.flip();
    for (auto& [x, y] : a) {
        reach_check &= can_reach[x][y];
        middle &= can_reach[x];
        end[y] = 1;
    }
    if (not reach_check) return 0;
    
    //for any valid middle, i need to make sure that it can
    //reach all the ends
    for (int i = 0; i < n; i++)
        if (middle[i])
            if ((can_reach[i] & end) == end)
                return 1;
    return 0;
}

void solve() {
    int n, m; cin >> n >> m;

    v<v<int>> adj(n), e(m);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[--a].push_back(--b);
        e[i] = {a, b};
    }

    tarjan(adj);
    sort(comps.begin(), comps.end());

    int k = 0;
    v<int> new_id(n, -1);
    for (int& u : comps)
        new_id[u] = k++;

    v<set<int>> build(n);
    for (int u = 0; u < n; u++)
        for (int& i : adj[u])
            if (comp[i] != comp[u])
                build[comp[u]].insert(comp[i]);
    
    v<v<int>> tree(k);
    for (int u = 0; u < n; u++)
        for (int i : build[u])
            tree[new_id[u]].push_back(new_id[i]);

    int q; cin >> q;
    v<array<int, 2>> a(q);
    v<array<int, 2>> b;
    for (auto& [x, y] : a) {
        cin >> x >> y;
        b.push_back({x - 1, y - 1});
        x = new_id[comp[--x]], y = new_id[comp[--y]];
    }
    bool ans = solve_dag(tree, a);
    // bool bf = bruteforce(tree, a);
    // if (ans != bf) {
    //     cout << "HERE" << nl;
    //     dbg(bf, ans);
    //     dbg(n, m);
    //     dbg(e);
    //     dbg(tree);
    //     exit(1);
    // }
    cout << (ans ? "YES" : "NO") << nl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // freopen("input.txt", "r", stdin);
    int T = 1;
    cin >> T;
    while (T--) solve();
}
Leave a Comment