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); } } };