P5058 嗅探器

问题

P5058 [ZJOI2004] 嗅探器
蓝军网络中有两个信息中心，两个中心之间可能存在多条不同的数据传输路线。需要选择一台既不是信息中心的中间服务器安装嗅探器，使两个中心之间交换的所有数据都必然经过它；若有多个选择则输出编号最小者，若不存在则输出 No solution。

数据规模：$n\le 2\times 10^5$，边数不超过 $5\times 10^5$。

找图上某一点使得源点和汇点的所有路线都经过它。

但如果直接求整张图的所有割点再取最小编号是错误的，因为一个割点可能只切断与 $a\to b$ 无关的支路。所以真正需要判断的是删除某个节点后，指定的两个信息中心是否断开。

以 $a$ 为 DFS 根，考虑祖先节点 $u$ 通向 $b$ 的那个 DFS 树儿子 $v$。当且仅当 $\operatorname{low}[v]\ge\operatorname{dfn}[u]$ 时，$v$ 的整棵子树无法绕过 $u$ 回到 $u$ 的祖先，因此删除 $u$ 会切断 $a$ 与位于该子树中的 $b$。

我的做法是在 tarjan(v) 刚返回时用 dfn[b] >= dfn[v] 判断 $b$ 是否位于 $v$ 子树。因为递归返回时，当前子树中的时间戳连续且不小于 dfn[v]，尚未搜索的兄弟分支时间戳为 $0$，已经结束的其他分支时间戳又更小，因此这里成立。这个判断依赖“刚从该儿子返回”的时机，若把统计移到 DFS 结束以后，就应额外记录子树时间戳区间。

最后特判节点 $a$ 与 $b$ 都不能作为中间服务器，按编号扫描标记即可得到最小解。

Tarjan 的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。

▶

P5058 嗅探器

struct Edge { int id, v; ll w; };
vector<Edge> adj[maxn];

int dfn[maxn], low[maxn], timer;
bool cut[maxn];
int a, b;

void add_edge( int u, int v, ll w, int id ) {
    adj[u].push_back({ id, v, w });
    adj[v].push_back({ id, u, w });
}

void tarjan( int u, int in_edge ) {
    dfn[u] = low[u] = ++ timer;
    for( auto [id, v, w] : adj[u] ) {
        if( !dfn[v] ) {
            tarjan( v, id );
            low[u] = min( low[u], low[v] );
            if( low[v] >= dfn[u] && u != a && dfn[b] >= dfn[v] ) {
                cut[u] = 1;
            }
        } else if( id != in_edge ) {
            low[u] = min( low[u], dfn[v] );
        }
    }
}

void solve( ) {
    int n = read( );
    int id = 0;
    while( 1 ) {
        int u = read( ), v = read( );
        if( u == 0 && v == 0 ) break;
        add_edge( u, v, 0, ++id );
    }
    a = read( ), b = read( );
    tarjan( a, 0 );
    for( int i = 1; i <= n; ++ i ) {
        if( cut[i] ) {
            cout << i << '\n';
            return;
        }
    }
    cout << "No solution" << '\n';
}

记录

• 归属：割点、指定两点连通性；

• 新增：整图割点不等于指定两点之间的必经点；必须只检查 DFS 树上通向目标点的分支，并使用该分支根的 low。

• 分类：待定