Untitled

mail@pastecode.io avatar
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;
}