题解：P3436 [POI 2006] PRO-Professor Szu

· · 题解

用 Kosaraju 的同志里边请。

也没人告诉我 Kosaraju 求图的部分点的强连通分量要加额外判断呀？？？

讲述我悲惨的调题经历。

首先，看到求 1\sim n 到 n+1，对于某点 i 要到 n+1，那把路径上的边全部反过来，就是从 n+1 到 1\sim n，所以我们反着建图。这样，我们知道了起点，就比较好做。

如果路径可以经过一个环（自环也行），那么可以无限套娃，不停转圈，方案数有无穷个。这时候想到对有向图缩点。如果某个强连通分量之中存在边，也可以说是存在两个点或存在自环，那么就有无穷个方案。如果该强连通分量只有一个点呢？那由他的前驱来转移，这是基础的缩点后在 DAG 上 DP。

以上就是本题的思路。

如果你和我一样使用 Kosaraju，并且第一次搜索只从 n+1 开始，那么会出现一些问题。回顾算法的流程，我们发现第一次搜索，记录了每个节点 i 的离开时间 l_i。如果两个节点 x,y 不在同一个 SCC，且 l_x > l_y，那么 y 不可达 x。如果 y 可达 x，只可能是 x,y 同属于一个 SCC，或者 l_y > l_x。

然后到第二次搜索，此时我们保证不会把其他 SCC 错误地访问的原因，是因为在缩点后的 DAG 中，该 SCC 的前驱已经被访问过了，该 SCC 的后继由于边被倒过来了，所以访问不到，而同一个 SCC 中边被倒过来是不会变动的。

但是，我们如果只 DFS 了一次，并不能保证某个 SCC 的所有前驱都被访问到了，n+1 不一定可到达某个前驱，所以就不对，比如下图。

这里是图片解释。当 n=2 时，蓝色边为原图，绿色边为取反后的图，3 只会到达 1。访问到 1 时，发现可以到达 2，并且 2 还没被访问过，于是 1,2 被放入同一个 SCC，于是就错了。解决的方法有两个：

  1. 用一个数组记录 n+1 可达的点，把不可达的点全部忽略。
  2. 先缩点全图，然后把入度为 0 的点都删去，但是保留 n+1。

本题还有一些其他的细节，可以看其他题解，有比较好的实现方法。

希望能增加屏幕前的你对 Kosaraju 的理解，这里提供一份实现。

#include<bits/stdc++.h>
using namespace std;
constexpr int N =1e6+10;
int n,m;
vector<int>e[N],re[N],ne[N];
int cir[N];

int vis[N],stk[N],c,scc[N];
void dfs(int u) {
    vis[u] = 1;
    for (int v : e[u]) {
        if (!vis[v]) dfs(v);
    }
    stk[++c] = u;
}
int tag;
void rdfs(int u) {
    scc[u] = tag;
    for (int v : re[u]) {
        if (!scc[v] && vis[v]) rdfs(v);
    }
}

int scccir[N],in[N],f[N];
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int x,y; cin>>x>>y;
        if (x == y) {
            cir[x] = 1;
        }
        else {
            e[y].push_back(x);
            re[x].push_back(y);
        }
    }
    dfs(n+1);
    for (int i=c;i;i--) {
        if (!scc[stk[i]] && vis[stk[i]]) tag++,rdfs(stk[i]);
    }
    for (int i=1;i<=n+1;i++) {
        if (scc[i] == 0) continue;
        if (cir[i]) scccir[scc[i]] = 1;
        for (int v : e[i]) {
            if (scc[v] == 0) continue;
            if (scc[i] == scc[v]) scccir[scc[i]] = 1;
            else {
                ne[scc[i]].push_back(scc[v]);
                in[scc[v]]++;
            }
        }
    }
    queue<int>q;
    q.push(scc[n+1]);
    f[scc[n+1]] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if (scccir[u] == 1) f[u] = 36501;
        for (int v : ne[u]) {

            f[v] = min(f[v] + f[u], 36501);
            in[v] --;
            if (in[v] == 0) q.push(v);
        }
    }
    int mx = 0;
    vector<int>ans;
    for (int i=1;i<=n;i++) {
        if (scc[i] == 0) continue;
        if (f[scc[i]] > mx) mx = f[scc[i]], ans.clear();
        if (f[scc[i]] == mx) ans.push_back(i);
    }
    if (mx == 36501) {
        cout << "zawsze\n";
    }
    else {
        cout << mx << '\n';
    }
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    return 0;
}

谨以此篇题解记录我逝去的一个夜晚和下午。