Untitled
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