WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM608 Div1 Medium "BigO"

問題

TopCoder Statistics - Problem Statement

猫のスヌークはプレゼントとして有向グラフを受け取った。

あなたはString[] graphが与えられる。graphの要素数は、彼が受け取ったグラフの頂点の数を表している。もしi番目の頂点からj番目の頂点へ、辺が伸びていた場合、graphのi番目の文字列のj番目の文字は'Y'となってる。辺がない場合、'N'となっている。

スヌークは、このグラフにおいて、距離L(Lは巨大)の歩き方はどれほどになるのか知りたくなった。Lだけ歩くとき、その方法(道筋の辿り方)の数は、O(L^K)と表せるのであれば、Kを返せ。表せなければ-1を返せ。

制約

1 <= 頂点数 <= 50


考えたこと

①...Div2の簡単版と同じく、複数の閉路に属する頂点が存在した場合、辿り方はO(2^L)となってしまう(2つの閉路に属する頂点が存在した場合)ので、-1

②...閉路が複数ある場合

例えば閉路Aと閉路Bがあって、A -> Bというパスがあった場合、歩いている中で、A -> Bへ移動するタイミングとして(Lは巨大なので)O(L)パターンとれる。

L = 5

A-A-A-A-A
A-A-A-A-B
A-A-A-B-B
A-A-B-B-B
A-B-B-B-B

よって、方法の数としてはO(L^1)となる。

さらに閉路Cがあって、B -> Cとなった場合(A -> B -> C)は、距離Lを歩いている中で、任意のタイミングで2回閉路を変更する事ができるので、O(L^2)パターン取れる。

L = 5

A-A-A-A-A
A-A-A-A-B
A-A-A-B-B
A-A-A-B-C
A-A-B-B-B
A-A-B-B-C
A-A-B-C-C
A-B-B-B-B
A-B-B-B-C
A-B-B-C-C
A-B-C-C-C

③...閉路が1つしかない場合
そこをぐるぐるするだけ。よってO(L^0)

④...閉路がない場合
巨大なLだけ歩けない。Sample1に従って0を返せばいいみたい。

実装

まず①のパターンでないか調べる。ある頂点sに着目したときに、s -> sにいける道筋が複数あればパターン①

そうでなければ、閉路単位での最長パスを調べればよい。まず強連結分解する。それから同じ閉路にある頂点を1つに縮約する。このグラフは閉路を持たないグラフになっている(いわゆるDAGってやつ)。そしたらこのグラフの閉路単位での最長パスを求めればよい。


ソースコード

int N;
vector<int> G[55]; // グラフ
vector<int> rG[55]; // 逆辺グラフ
vector<int> cmpG[55]; // 強連結グラフ
vector<int> vs; // 強連結分解用
int cmp[55]; // 強連結成分番号
bool used[55]; // 使用済み?
bool isLink[55]; // これ閉路?
int dp[55];

class BigO {

    public:

    int minK(vector <string> graph) {

        N = graph.size();

        // グラフ作成
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (graph[i][j] == 'Y') {
                    G[i].push_back(j);
                    rG[j].push_back(i);
                }
            }
        }

        // パターン①かどうかを調べる
        for (int v = 0; v < N; v++) {
            memset(used, 0, sizeof(used));
            if (cntPath(v, v) > 1) {
                return -1;
            }
        }

        // 強連結成分分解
        scc();

        // 強連結成分でグラフを縮約
        for (int cs = 0; cs < N; cs++) {
            memset(used, 0, sizeof(used));
            for (int s = 0; s < N; s++) {
                if (cmp[s] != cs) continue;
                for (int i = 0; i < G[s].size(); i++) {
                    int t = G[s][i];
                    int ct = cmp[t];
                    if (cs == ct) continue;
                    if (used[ct]) continue;
                    cmpG[cs].push_back(ct);
                    used[ct] = true;
                }
            }
        }

        // 閉路判定
        chkLink();

        // 閉路単位での最長パスを調べる
        int res = 0;
        for (int i = 0; i < N; i++) {
            dp[i] = -2;
        }
        memset(used, 0, sizeof(used));
        for (int i = 0; i < N; i++) {
            res = max(res, solve(i));
        }

        return res;
    }

    // 頂点vからスタートして、閉路単位での最長パスを求める
    int solve(int v){
        int& m = dp[v];
        if (m != -2) return m;

        used[v] = true;

        int res = -1;

        for (int i = 0; i < cmpG[v].size(); i++) {
            int to = cmpG[v][i];
            if (used[to]) continue;
            int cand = solve(to);
            if (isLink[v]) cand++;
            res = max(res, cand);
        }

        used[v] = false;

        if (res == -1 && isLink[v]) res = 0;

        return m = res;
    }

    // 頂点sからtまでの行き方の数
    int cntPath(int s, int t) {
        used[s] = true;

        int res = 0;

        for (int i = 0; i < G[s].size(); i++) {
            int to = G[s][i];
            if (to == t) {
                res++;
                continue;
            }
            if (!used[to]) res += cntPath(to, t);
        }

        return res;
    }

    // 閉路判定(強連結成分ごとで、複数の頂点が属しているか)
    void chkLink(){
        memset(isLink, 0, sizeof(isLink));
        for (int i = 0; i < N; i++) {
            int cnt = 0;
            for (int j = 0; j < N; j++) {
                if (i == cmp[j]) cnt++;
            }
            if (cnt > 1) isLink[i] = true;
        }
    }

    // 強連結成分分解を行う
    void scc(){
        memset(used, 0, sizeof(used));
        for (int v = 0; v < N; v++){
            if (!used[v]) dfs(v);
        }
        memset(used, 0, sizeof(used));
        int k = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (!used[vs[i]]) dfs2(vs[i], k++);
        }
    }

    void dfs(int v){
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++){
            if (!used[G[v][i]]) dfs(G[v][i]);
        }
        vs.push_back(v);
    }

    void dfs2(int v, int k){
        used[v] = true;
        cmp[v] = k;
        for (int i = 0; i < rG[v].size(); i++) {
            if (!used[rG[v][i]]) dfs2(rG[v][i], k);
        }
    }
};