次のサイトを参考にさせていただきました。
一応自分で使いやすい感じにカスタマイズさせていただきました。
強連結成分分解(Strongly-Connected-Components) | Luzhiled’s memo

解説

トポロジカルソートの要領で各頂点からdfsして、帰りがけに頂点を追加していきます。
次に、追加した頂点を始点として、辺を逆に張ったグラフ上でdfsをします。このとき、その頂点から行くことの出来た頂点は同じ強連結成分に含まれます。
詳しい証明などは他のサイトにまかせるとして、メインアイディアは、「連結成分なんだから、辺を逆に張ったグラフ上でも行き来できる」というものです。
かなり多めにコメントを書いたのでそちらを読んで頂くとわかりがいいと思います。

コード

verifyは、下記のaojの問題で行いました。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C&lang=jp

提出コードです。
AIZU ONLINE JUDGE: Code Review

using namespace std;

struct StronglyConnectedComponents {

    //受け取るグラフ, 順方向に辺を張ったグラフ, 逆方向に辺を張ったグラフ
    vector<vector<int>> g, ng, rg;

    //頂点の色, 帰りがけ順, 訪問済みかどうか
    vector<int> nd_color, tp_order, visited;

    //コンストラクタ
    StronglyConnectedComponents(vector<vector<int>>& g) : g(g), ng(g.size()), rg(g.size()), nd_color(g.size(), -1), visited(g.size()) {
        for (int v = 0; v < g.size(); v++) {
            //ng, rg を構築
            for (auto nv : g[v]) {
                ng[v].push_back(nv);//順方向
                rg[nv].push_back(v);//逆方向に辺を張りなおす
            }
        }
    }

    //頂点vから開始して帰りがけに頂点を追加していく
    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (auto nv : ng[v]) dfs(nv);
        tp_order.push_back(v);
    }


    //逆方向のグラフに対してdfsして、強連結成分をcolorで塗ります
    void rdfs(int v, int color) {
        if (nd_color[v] != -1) return; //既に彩色されてたら取りやめる

        nd_color[v] = color;
        for (auto nv : rg[v]) rdfs(nv, color);
    }

    //強連結成分ごとに彩色します
    void color_graph() {

        //順方向のグラフにdfs(トポロジカルソートの要領で全点から)
        for (int i = 0; i < ng.size(); i++) {
            dfs(i);
        }
        //得られた順序は逆順なのでreveseします
        reverse(tp_order.begin(), tp_order.end());

        //帰りがけ順にrdfsします
        int color = 0;
        for (auto ord : tp_order) {
            if (nd_color[ord] == -1) {
                rdfs(ord, color);
                color++;
            }
        }
    }

    //強連結成分を1つの頂点に見立てたグラフを構築します(多重辺が含まれるので注意です!)
    vector<vector<int>> build() {

        //グラフの彩色数を求めます。
        int color_n = 0;
        for (auto c : nd_color) {
            color_n = max(color_n, c);
        }

        vector<vector<int>> ret(color_n + 1); //彩色数が頂点数になっています


        //隣接する頂点v,uについて考えたとき、両者の色が異なれば異なる強連結成分です
        for (int v = 0; v < g.size(); v++) {
            int v_c = nd_color[v];
            for (auto nv : g[v]) {
                int u_c = nd_color[nv];
                if (v_c != u_c) ret[v_c].push_back(u_c); //vの色からuの色に対して辺を張ります
            }
        }

        return ret;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    StronglyConnectedComponents scc(G);
    scc.color_graph();

    auto color = scc.nd_color;

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << (color[u] == color[v]) << endl;
    }
}