Substring [Codeforces Round #460 D]

http://codeforces.com/contest/919/problem/D

N頂点M辺の有向グラフがある。
各頂点には文字が割り当てられている。
任意のパスを選んで文字列を作るとする。
文字列の中で最も多く出てくる文字の数をポイントとするとき、最大ポイントは？
最大ポイントを無限に増やせる場合は-1を出力。

前提知識

• トポロジカルソート

解法

http://codeforces.com/contest/919/submission/34776210

まず、無限に増やせる場合を考えてみよう。
有向グラフにサイクルがあるなら無限に増やせることが分かる。
その為、サイクルが存在するなら-1を出力し、存在しないなら最大ポイントの計算に入ればよさそう。
サイクルが存在しない有向グラフはDAGと呼ばれ、DPできるので、DPしよう。
「dp[node][c] := nodeで終わるパスの中で文字cが出てくる最大値」
これを更新するが、dp[node]を計算するには遷移先にnodeが含まれる頂点を先に計算しておく必要がある。
この計算順を考えてみると、丁度トポロジカルソート順となっている。
そのため、トポロジカルソートをして、その順番にDP更新をしていこう。
最後にdp[node][c]の最大値を取ると答え。

int N, M;
vector<int> E[301010];
string S;
int dp[301010][30];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S;
    TopologicalSort ts(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        ts.add_edge(a, b);
        E[a].push_back(b);
    }
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    int res = ts.sort(ord);
    if (res == 0) {
        printf("-1\n");
        return;
    }

    rep(i, 0, N) dp[i][S[i] - 'a'] = 1;

    rep(_, 0, N) {
        int i = ord[_];

        fore(to, E[i]) {
            int c = S[to] - 'a';
            rep(j, 0, 26) {
                if (c == j) chmax(dp[to][j], dp[i][j] + 1);
                else chmax(dp[to][j], dp[i][j]);
            }
        }
    }

    int ans = 0;
    rep(i, 0, N) rep(j, 0, 26) chmax(ans, dp[i][j]);
    cout << ans << endl;
}