[TopCoder 13001] BigO 题解

题目描述

给定一张有向图，当 \(L\) 趋近于无穷大时，长度为 \(L\) 的路径条数有 \(S\) 条，此时若 \(S = O(L^k)\)，输出 \(k\)，否则如果没有多项式的大 O 表示法，输出 \(-1\)。

指数情况

首先如果一张图中存在如下强连通分量，则 \(S = O(2^L)\)。

因为每次到 1 号点的时候都有两种选择，一种是直接回到 2，另一种是通过 3 绕回 2，从 2 回到 1 只有一种可能，所以按大 O 表示法，忽略常数，\(S = O(2^L)\)。

大胆猜测，对于一个 SCC，如果它不恰好为一个环，则它的路径条数是指数级别的。

以下给出证明：

如果一个 SCC 不是环，那么它的环上一定有一条伸出去的边，这条边连到的节点如果不在环上，那么一定能够找到一条路径回到 SCC，这条路径就形成了上图中的 \(a\rightarrow b\)。

如果从 \(b\) 出发，有两种路径回来，一个是经过 ... 所代表的路径，一个是经过 \(2\rightarrow 3\rightarrow 4\) 所代表的路径，它们的长度都是 \(O(n)\) 级别的，那么长度为 \(L\) 的路径条数就是 \(O(2^{\frac{L}{n}})\) 级别的，省略掉 \(n\)，就是 \(O(2^L)\) 级别的。

多项式情况

分类讨论以下

\(O(L^0)\)

如果图中只有单个的环，那么只有一种走法就是一直绕，所以路径条数是常数条的，可以写作 \(O(L^0)\)。

\(O(L)\)

如果一个环 \(A\) 指向了另一个环 \(B\)，那么如果从环 \(A\) 出发，我们可以选择绕不超过 \(\lfloor\dfrac{L}{|A|}\rfloor\) 次环 \(A\) 再走到环 \(B\)，对于 \(L\) 而言，\(|A|\) 是常数，所以最后路径条数就是 \(O(L)\) 的。

\(O(L^k)\)

这种情况出现当且仅当存在一条链，并且链上 SCC 大小 \(> 1\) 的 SCC 个数为 \(k\)。

可以感性理解，类比上述情况。

综上所述

SCC 缩点之后，一定会形成一张 DAG，这个 DAG 上有很多条链，而多条链互相是不会影响的，由于大 O 表示法只保留最大的指数，所以最终答案就是 DAG 上的最长链长度，注意这里长度的定义是链上 SCC 大小 \(> 1\) 的 SCC 个数，因为单点是不会产生贡献的。

C++ 实现

注意 TopCoder 的题目需要写到一个指定的类里面。

时间复杂度：\(O(n + m)\)。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 50 + 10;

vector<int> g[N], ig[N];
int n;
void init(vector<string> G) {
    n = G.size();
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(G[i][j] == 'Y')
                g[i + 1].push_back(j + 1);
}

int dfn[N], low[N], timestamp, stk[N], in_stk[N], scc_cnt, sz[N], id[N], top, cnt[N];
void tarjan(int p)
{
    dfn[p] = low[p] = ++ timestamp;
    stk[++ top] = p, in_stk[p]= true;
    for(auto j : g[p]) {
        if(!dfn[j]) tarjan(j), low[p] = min(low[p], low[j]);
        else if(in_stk[j]) low[p] = min(low[p], dfn[j]);
    }
    if(dfn[p] == low[p]) {
        int y;
        scc_cnt ++;
        while(y != p) {
            y = stk[top --];
            in_stk[y] = 0, id[y] = scc_cnt, sz[scc_cnt] ++;
        } 
    }
}

int f[N];

int work() {
    for(int i = 1; i <= n; i ++)
        if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i ++)
        for(auto j : g[i]) {
            if(id[i] == id[j])
                cnt[id[i]] ++;
            else 
                ig[id[i]].push_back(id[j]);
        }
    for(int i = 1; i <= scc_cnt; i ++)
        if(cnt[i] > sz[i])
            return -1;
    int ans = 0;
    memset(f, -0x3f, sizeof f);
    for(int i = 1; i <= scc_cnt; i ++) {
        f[i] = -1;
        for(auto j : ig[i])
            f[i] = max(f[i], f[j]);
        f[i] += (sz[i] > 1);
        ans = max(ans, f[i]);
    }
    return ans;
}

class BigO {
    public :
        int minK(vector<string> graph) {
            init(graph);
            return work();
        }
} ;