P9166 解题报告

· · 题解

一个比较暴力的做法。

首先发现：编号比 x 小的点能最后到达的必要条件是其为某条铁路线的左端点，编号比 x 大的点同理。

我们考虑：对于一条铁路线 [l,r]，直接 \forall i\in[l,r)，连无向边 (i,i+1)。

这样只有在最终构成的图上与起点 x 在同一连通块上的点才可能是答案。
不难发现结合上面的性质就是充要条件了。

但是直接暴力建是 \mathcal{O(n^2)} 的，不够优。

发现有很多重复边，实际上每个点最多只有两条边是有用的，即向左右相邻连的两条边。

类似这个题，我们可以利用并查集来优化区间覆盖。

具体实现看代码：

const int N=2e5+3;
int n,m,st,fa[N],vis[N];
std::vector<int>G[N];
bool L[N],R[N];
il int get(int x)
{
    for(;x^fa[x];x=fa[x]=fa[fa[x]]);
    return x;
}
il void dfs(re int u)
{
    vis[u]|=1;
    for(re int v:G[u]) !vis[v]&&(dfs(v),7);
}
void Solve()
{
    rd(n),rd(m),rd(st);
    for(re int i=1;i<=n;++i) fa[i]=i;
    for(re int l,r;m--;)
    {
        rd(l),rd(r),L[l]|=1,R[r]|=1;
        for(;l<r;r=fa[r])
            if(get(r)==r) G[r].pb(r-1),G[r-1].pb(r),fa[r]=get(r-1);
    }
    dfs(st);
    for(re int i=1;i<st;++i) vis[i]&&L[i]&&(prt(i,' '));
    for(re int i=st+1;i<=n;++i) vis[i]&&R[i]&&(prt(i,' '));
    return;
}