強連結成分分解

vector<vector<int>> scc(int n,const vector<vector<int>>& v){
    vector<vector<int>> vv(n);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < v[i].size();j++){
            vv[v[i][j]].push_back(i);
        }
    }
    vector<int> res;
    vector<bool> visited(n,false);
    function<void(int)> f = [&](int pos){
        visited[pos] = true;
        for(int i : v[pos]){
            if(!visited[i])f(i);
        }
        res.push_back(pos);
    };
    for(int i = 0;i < n;i++){
        if(!visited[i]){
            f(i);
        }
    }
    vector<vector<int>> ans;
    visited.assign(n,false);
    for(int i = res.size()-1; i >= 0;i--){
        if(visited[res[i]])continue;
        vector<int> p = {res[i]};
        function<void(int)> d = [&](int pos){
            visited[pos] = true;
            for(int i : vv[pos]){
                if(visited[i])continue;
                p.push_back(i);
                d(i);
            }
        };
        d(res[i]);
        ans.push_back(p);
    }
    return ans;
}