P1656 炸铁路

问题

P1656 炸铁路
B 国的城市由双向铁路连接，并且原本任意两座城市之间都可以互相到达。现在只能炸毁一条铁路，需要找出所有会使交通网失去连通性的铁路，并按端点编号顺序输出。

数据规模：$n\le 150$，$m\le 5000$。

当然本题由于数据规模小，朴素的做法可以直接暴力枚举每一条边。

不过本题还可以采用更通用的 Tarjan 求割边(桥)算法。

对于 DFS 树边 $u\to v$，$\operatorname{low}[v]$ 表示 $v$ 的子树不经过父边能够到达的最早时间戳。若满足 $\operatorname{low}[v]>\operatorname{dfn}[u]$，说明这棵子树无法通过任何返祖边回到 $u$ 或更高祖先，因此父边 $(u,v)$ 是桥。

这里必须使用严格大于，因为 $v$ 的子树只要还能绕回 $u$ 本身，父边就存在替代路径。割点常见的条件是 $\operatorname{low}[v]\ge\operatorname{dfn}[u]$，不过它判断的是删除父节点后的连通性，DFS 根还要结合儿子数量单独处理，不能只把符号替换后机械套用。

Tarjan 的时间复杂度为 $O(n+m)$，最后排序桥的复杂度为 $O(B\log B)$，其中 $B$ 是桥的数量。空间复杂度为 $O(n+m)$。

▶

P1656 炸铁路

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

int dfn[maxn], low[maxn], timer;

bool bridge[maxm];
int bcnt;
vector< pair<int, int> > res;

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] ) {
                res.push_back({ min( u, v ), max( u, v ) });
                bridge[id] = true;
                ++ bcnt;
            }
        } else if( id != in_edge ) {
            low[u] = min( low[u], dfn[v] );
        }
    }
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        add_edge( u, v, 0, i );
    }
    for( int i = 1; i <= n; ++ i ) {
        if( !dfn[i] ) tarjan( i, 0 );
    }
    sort( res.begin( ), res.end( ) );
    for( auto [u, v] : res ) {
        printf( "%d %d\n", u, v );
    }
}

记录

• 归属：桥、边双连通分量；
• 新增：桥使用严格条件 low[v] > dfn[u]，并且输出前要把无向边端点规范化后再排序。
• 分类：待定