题解：P14799 [JOI 2026 二次预选] 比太郎之旅 3 / Bitaro's Travel 3

· · 题解

题目传送门

题意简述

给定一个 无向简单图。

一条路径合法，满足相邻两点有边，且编号大小交替（小→大→小→大，奇数步升、偶数步降），允许重复经过点。

求每个点无论如何都无法通过合法路径到达的点的个数。

思路

显然将问题转化为求可达点的数量会更加好做。

如果每一个节点都跑一遍 dfs，显然是会 TLE 的，所以我们考虑在一次 dfs 中尽可能地多求出一些点的答案。

如图，以 1 号节点为起点走出的合法路径上，每个红色节点都处于相同相位（下一步方向一致）。由于合法性只取决于大小交替，以这些红色节点为起点也会走出结构相同的路径。于是一次 dfs 就能同时求出这一组点的答案。

观察图片中的白色节点，会发现与它们相连的节点全部比它们大，所以这条路径不适用于它们，那么它们就还需要再次 dfs。由于遍历过程中还是有可能重复，我们仍然需要标记它们，只不过要与红色区分。

所以每个点需要分两种状态分别标记，设 vis_{i,0/1} 表示从比它大/小的节点来到它，只需要遇到 vis_{i,0}=0 就可以去遍历那一组点，同时记录所有红色节点的答案。

时间复杂度 O(N+M)。

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;

int p,ans[3000005],cnt,vis[3000005][2];
vector<int>g[3000005],vc;

void dfs(int u,int fa,int zt){
    vis[u][zt]=p;
    if(vis[u][zt^1]!=p)cnt++;
    if(zt==0)vc.push_back(u);
    for(auto v:g[u]){
        if(v==fa)continue;
        if(zt==0){
            if(v<u||vis[v][1])continue;
            dfs(v,u,1);
        }else{
            if(v>u||vis[v][0])continue;
            dfs(v,u,0);
        }
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(vis[i][0])continue;
        p++;
        cnt=0;
        vc.clear();
        dfs(i,-1,0);
        for(int i=0;i<vc.size();i++){
            ans[vc[i]]=cnt;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<n-ans[i]<<endl;
    }
    return 0;
}