Untitled
unknown
plain_text
a year ago
2.2 kB
5
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define make_it_faster std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define endl "\n" #define all(x) x.begin(), x.end() #define pb push_back const int MOD = 1e9+7; const int MAX = 1e5+10; const int INF = 0x3f3f3f3f3f3f3f3f; int up[MAX], vis[MAX]; bool incycle[MAX], vis2[MAX]; vector<vector<int>> adj(MAX); class DSU{ public: vector<int> parent, sz; void make(int v){ parent[v] = v; sz[v] = 1; } int find(int v){ if (v == parent[v]) return v; return parent[v] = find(parent[v]); } void union_(int a, int b){ a = find(a), b = find(b); if(sz[b]>sz[a]) swap(a,b); if (a != b){ sz[a] += sz[b]; parent[b] = a; } } bool same(int a, int b){ a = find(a), b = find(b); return a == b; } DSU(int n): parent(n+1), sz(n+1){ for(int i=1; i<=n; i++) make(i); } }; void dfs(int v, int p){ if(vis[v] == 2) return; if(vis[v] == 1){ vector<int> vec; int cur = p; incycle[cur] = true; while(cur != v){ cur = up[cur]; incycle[cur] = true; } return; } up[v] = p; vis[v] = 1; for(auto it: adj[v]){ if(p == it) continue; dfs(it, v); } vis[v] = 2; } void dfs2(int v, DSU &dsu){ vis2[v] = true; for(auto it: adj[v]){ if(incycle[it] or vis2[it]) continue; dsu.union_(v, it); dfs2(it, dsu); } return; } int32_t main(){ make_it_faster; int n, m, q; cin >> n >> m >> q; for(int i=0; i<m; i++){ int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } for(int i=1; i<=n; i++){ dfs(i, i); } DSU dsu(n); for(int i=1; i<=n; i++){ if(!vis2[i] and !incycle[i]){ dfs2(i, dsu); } } while(q--){ int a, b; cin >> a >> b; if(dsu.same(a, b)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }