Test/AOJ/StronglyConnectedComponent.test.cpp

View this file on GitHub
Last update: 2023-07-31 10:53:01+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/StronglyConnectedComponent.cpp"

int main() {
    int N,M;
    cin >> N >> M;
    SCC scc(N);
    for(int i = 0;i < M;i++) {
        int s,t;
        cin >> s >> t;
        scc.add_edge(s,t);
    }
    scc.scc();
    int Q;
    cin >> Q;
    for(int i = 0;i < Q;i++) {
        int u,v;
        cin >> u >> v;
        cout << scc.same(u,v) << endl;
    }
}

#line 1 "Test/AOJ/StronglyConnectedComponent.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Graph/StronglyConnectedComponent.cpp"
class SCC {
    int n;
    std::vector<std::vector<int>> graph;
    std::vector<std::vector<int>> rgraph;//辺を逆にはったグラフ
    std::vector<int> vs; //帰りがけ順の並び
    std::vector<bool> used; //既に頂点に訪れたか
    std::vector<int> cmp; //属する強連結成分のトポロジカル順序


    void dfs(int v) {
        used[v] = true;
        for(auto x:graph[v]) {
            if(not used[x]) dfs(x);
        }
        vs.push_back(v);
    }

    void rdfs(int v,int k) {
        used[v] = true;
        cmp[v] = k;
        for(auto x:rgraph[v]) {
            if(!used[x]) rdfs(x,k);
        }
    }

public:

    SCC(int n): n(n) {
        graph.resize(n);
        rgraph.resize(n);
        used.resize(n);
        cmp.resize(n);
    }

    void add_edge(int from,int to) {
        graph[from].push_back(to);
        rgraph[to].push_back(from);
    }

    //返り値は分解した後の頂点の数
    int scc() {
        vs.clear();
        for(int v = 0;v < n;v++) {
            if(not used[v]) dfs(v);
        }

        for(int i = 0;i < n;i++) {
            used[i] = false;
        }

        int k = 0;
        for(int i = vs.size() - 1;i >= 0;i--) {
            if(not used[vs[i]]) rdfs(vs[i],k++);
        }
        return k;
    }

    int operator[](int k) {return cmp[k];}

    bool same(int a,int b) {
        return cmp[a] == cmp[b];
    }
};
#line 8 "Test/AOJ/StronglyConnectedComponent.test.cpp"

int main() {
    int N,M;
    cin >> N >> M;
    SCC scc(N);
    for(int i = 0;i < M;i++) {
        int s,t;
        cin >> s >> t;
        scc.add_edge(s,t);
    }
    scc.scc();
    int Q;
    cin >> Q;
    for(int i = 0;i < Q;i++) {
        int u,v;
        cin >> u >> v;
        cout << scc.same(u,v) << endl;
    }
}