強連結成分分解とARC030C-有向グラフ

強連結成分分解

パソコン甲子園予選お疲れ様でした
僕は7問目で詰まって時間を溶かした結果、解けたであろう9問目を解けず7問目すら解けず終了しました
会津オフ会楽しんできてください

ところで10問目が強連結成分分解でしたね
強連結成分分解ということはわかったのですがライブラリ持ってないからと諦めたのでやりました

基本的にはうしさんのを参考にしました
それに、強連結成分をまとめた後のグラフ、それぞれの強連結成分に含まれる頂点の番号を返せるようにしたものがこちらです

class SCC{
private:
    vector<vector<int> > gg, rg;
    vector<int> order, comp;
    vector<bool> used;
    vector<vector<int> > ng, vs;

    int n, nn;
public:
    SCC(){}
    SCC(int v) : gg(v), rg(v), comp(v, -1), used(v, 0), n(v){}

    void add_edge(int x, int y){
        gg[x].push_back(y);
        rg[y].push_back(x);
    }

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

    void dfs(int v){
        used[v] = true;
        REP(i, gg[v].size()){
            if(!used[gg[v][i]]) dfs(gg[v][i]);
        }
        order.push_back(v);
    }

    void rdfs(int v, int k){
        used[v] = true;
        comp[v] = k;
        REP(i, rg[v].size()){
            if(!used[rg[v][i]]) rdfs(rg[v][i], k);
        }
    }

    int build(){
        REP(i, n){
            if(!used[i]) dfs(i);
        }
        fill(all(used), 0);
        int k = 0;
        for(int i = order.size()-1;i >= 0;i--){
            if(!used[order[i]]) rdfs(order[i], k++);
        }
        nn = k;

        //---------それぞれの強連結成分に含まれる頂点の番号----------
        vs.resize(k, vector<int>());

        REP(i, n)
            vs[comp[i]].push_back(i);
        //-----------------------------------------------------------

        //---------強連結成分をまとめた後のNew Graph!----------------
        ng.resize(k, vector<int>());
        REP(i, n){
            REP(j, gg[i].size()){
                if(comp[i] != comp[gg[i][j]])
                    ng[comp[i]].push_back(comp[gg[i][j]]);
            }
        }
        REP(i, nn){
            sort(all(ng[i]));
            ng[i].erase(unique(all(ng[i])), ng[i].end());
        }
        //------------------------------------------------------------
        return k;
    }
    
    int size(){
        return nn;
    }

    vector<vector<int> > graph(){
        return ng;
    }

    vector<int> vertices(int v){
        return vs[v];
    }
};

長いですね
おそらく変数名とか把握できてないので書き換えはもうできません
とりあえず某でverify的なのもしたところ(もとがうしさんのなのでもちろん通りましたが) 某氏に、ARC030Cを解けと薦められたので苦労の末ときました

ARC030C 有向グラフ

ARC-Eの何かしらを解けと言われた後、AtCoderProblemsでこれかな？って開いた後、難しそうだからいっか！みたいに閉じました
後からしっかりこの問題を名指しされたのではいってなって解くことにしました

明らかにSCCなのはわかり、することもわかり、実装も順調に進んでました
大体1時間ぐらいで最初の提出は出来ましたね
その後WAの原因がわからず死んでました
ときにはSCCの部分が間違ってるのではと思うこともありましたが気づきました

dfsの始点を最初に与えられた辺で入次数が0の頂点にしてたんですが、強連結成分が始点になるべきときに死んでました
強連結成分分解後に入次数0の頂点を始点として行えば成功しました(いえい)

解法

SCC
入次数が0の頂点を始点にして以下のDFSをする
- dp[i][j] := 頂点iまでの文字から作ったj文字での辞書順最小の文字列を持つ
- 各強連結成分ごとに含まれる文字をソートしたものを持つ
  - ここで各強連結成分に含まれる頂点の番号を返すやつが役に立ちます
- あとはDAGを辿り一つ前の頂点の情報を元に貰うDPっぽいのをします
- うまく結果を返す方法が思いつかなかったから適当にやってます
- 始点の時はあからさまな例外処理をしてるね
なんか通る

int n, m, k;
char c[310];
SCC scc;
vector<vector<int> > G;
string dp[310][310] = {};
string res;

void dfs(int v, int p){
    vector<int> vs = scc.vertices(v);
    string s = "";
    REP(i, vs.size())
        s = s+c[vs[i]];
    sort(all(s));

    if(p != -1){
        REP(i, 310){
            REP(j, min(i, (int)s.size())+1){
                dp[v][i] = min(dp[p][i], min(dp[v][i], dp[p][i-j]+s.substr(0, j)));
            }
        }
    }else{
        REP(i, s.size()+1)
            dp[v][i] = s.substr(0, i);
    }
    REP(i, G[v].size()){
        dfs(G[v][i], v);
    }
    res = min(res, dp[v][k]);
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m >> k;
    REP(i, n)
        cin >> c[i];
    scc = SCC(n);
    REP(i, m){
        int a, b;
        cin >> a >> b;
        scc.add_edge(a-1, b-1);
    }
    scc.build();
    G = scc.graph();

    REP(i, 310)
        fill(dp[i], dp[i]+310, string(400, 'z'));
    res = string(400, 'z');
    vector<int> v(scc.size(), 0);

    REP(i, G.size()){
        REP(j, G[i].size()){
            v[G[i][j]]++;
        }
    }
    REP(i, v.size()){
        if(v[i] == 0){
            dfs(i, -1);
        }
    }

    if(res == string(400, 'z'))
        cout << -1 << endl;
    else
        cout << res << endl;
}

とても長かった
SCCつらいね

次は2SAT解いた後HL分解やります

迷いませんか？

継続しないを座右の銘に

強連結成分分解とARC030C-有向グラフ

強連結成分分解

ARC030C 有向グラフ

解法