Submission #71498066

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/scc>
typedef long long ll;
using namespace std;

void dfs(int u, vector<vector<int>>& G, vector<bool>& visited){
    visited[u] = true;

    for(int v : G[u]){
        if(!visited[v]){
            dfs(v, G, visited);
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    int X[m], Y[m];
    for(int i = 0; i < m; i++){
        cin >> X[i] >> Y[i];
        X[i]--; Y[i]--;
    }

    atcoder::scc_graph graph(n);
    for(int i = 0; i < m; i++) graph.add_edge(X[i], Y[i]);

    auto scc = graph.scc();
    int K = scc.size();
    vector<int> idx(n);
    for(int i = 0; i < K; i++){
        for(auto u : scc[i]) idx[u] = i;
    }

    vector<vector<int>> G(K);
    for(int i = 0; i < m; i++){
        if(idx[X[i]] == idx[Y[i]]) continue;
        G[idx[Y[i]]].push_back(idx[X[i]]);  // 逆向きの辺
    }

    for(int i = 0; i < K; i++){
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
    }

    int q;
    cin >> q;

    vector<bool> visited(K, false);
    while(q--){
        int t,v;
        cin >> t >> v;
        v--;

        if(t == 1){
            if(!visited[idx[v]]) dfs(idx[v], G, visited);
        }else{
            if(visited[idx[v]]) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    
}

Submission Info

Judge Result