P12954 [GCJ Farewell Round #2] Railroad Maintenance 题解

Coding_caopy · 2026-08-09 21:02:53 · 题解

问题简述

有 N 个车站和 L 条铁路线。每条铁路线服务若干个车站（车站不重复）。乘客可以在任意车站换乘，只要两条线路有共同车站即可。初始时整个网络连通（任意两站之间都有路径）。

定义一条铁路线为关键线路，若关闭该线路后，会导致至少一对车站之间无法到达。求关键线路的数量。

我们首先发现，直接遍历线路删除根本不可做，因为一条线路链接的点太多，删除后要白费很多事，所以我们能否把路线压缩一下呢？

于是

我们考虑一个“线路 – 车站”的包含关系。

如果直接看车站之间的连通性，换乘关系由“是否被同一条线路服务”决定，所以我们有理由将一条路线压缩成一个点，具体如何做呢？

我们可以建立如下的无向图：

• 每个车站对应一个节点（编号 1 \sim N）；
• 每条铁路线也对应一个节点（编号 N+1 \sim N+L）；
• 若车站 x 属于线路 i，则在节点 x 与节点 N+i 之间连一条无向边。

这样，原铁路网络的连通性就完全等价于这个无向图的连通性。

因为：

• 两个车站之间若可达，则它们在图中对应节点之间必有路径（路径由车站节点和线路节点交替组成）；
• 反过来，任何一条由车站节点和线路节点交替构成的路径，都对应一组可以换乘的线路，实现车站间的可达。

因此，删除一条线路，就等价于在图中删除对应的线路节点。如果删除该节点后图不再连通，则该节点就是图的一个割点。

最后统计答案就很简单，只需要记录计所有被标记为割点的节点中，编号大于 N 的（即线路节点）的数量，即为答案。

（割点不会的快去学啊啊啊啊！）

复杂度分析

• 建图边数 S = \sum K_i，其中 K_i 为每条线路服务的车站数量。
• 总节点数 V = N + L。
• Tarjan 算法复杂度 O(V + S)，在题目给定的数据范围（N, L \le 10^5，S \le 2\times 10^5）内完全可行。

实现细节

• 多测不清空——
• 只统计线路，不要统计节点
• 割点板子别废了

参考代码

//忠誠老實
//為民而流血，為己而流淚，鄭洞囯將軍
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=3e5+5;
int n,L;
int dfn[N],low[N],siz[N],cut[N];
int clk,cnt;
vector<int>adj[N];

void clean(){
    for(int i=0;i<=n+L;i++){
        dfn[i]=low[i]=siz[i]=cut[i]=0;
        adj[i].clear();
    }
    clk=cnt=0;
}

void tarjan(int u,int fa){
    dfn[u]=low[u]=++clk;
    for(int v:adj[u]){
        if(v==fa) continue;
        if(!dfn[v]){
            siz[u]++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) cut[u]=1;
        }else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==0&&siz[u]<2) cut[u]=0;  // 根节点特判
    if(cut[u]&&u>n) cnt++;   // 只统计线路节点
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;
    cin>>T;
    for(int tc=1;tc<=T;tc++){
        cin>>n>>L;
        clean();
        for(int i=1,k;i<=L;i++){
            cin>>k;
            while(k--){
                int x;
                cin>>x;
                adj[n+i].push_back(x);
                adj[x].push_back(n+i);
            }
        }
        tarjan(1,0);   // 图连通，从 1 开始
        cout<<"Case #"<<tc<<": "<<cnt<<'\n';
    }
    return 0;
}