P11812

wuyixiang · 2026-10-23 15:52:00 · 题解

题目传送门

来自思维训练的 A。BCDE 全是青但是 A 是黑的思维训练也是神了，于是就有了我的第一篇黑题题解。

另外这道题有双倍经验 CF982F，但是数据更强。

题目大意

给你一个有向图，请输出所有回路点集的交，若不存在回路输出 NIE。

思路分析

首先只看点是不好做的，考虑先找一个环，这样所有满足条件的点肯定在这个环上。

找环可以用 Tarjan 来解决，维护一个栈就可以了。

没有找到环显然输出 NIE。

然后我们需要判断的就是：这个环上经过的点中，哪些是合法的？

不难发现当且仅当把这个点以及连接这个点的所有边全部删去后图不存在环。

但是如果我们一个一个去删点，最坏复杂度是 \mathcal{O}(n^2) 的，无法接受，我们需要优化。

我们换一个思路：还是枚举环上的每一个点。但是这次我们只需要知道从这个点开始，只经过非环边所能到达的环上最远点。

也就是说，设枚举的点为 x，我们想要找到一个点 y，使得 y 在环上且 x 经过环边到达点 y 经过的环边数量最多，且 y 可以由 x 只经过非环边到达。

这是什么意思？画一张图。

蓝边是我们找到的环，红边是环外的边，黄点是我们枚举的点。它可以沿着非环边走到绿点和紫点两个环点，但是紫点离黄点的距离更远（注意距离在这里有不同的定义），因此我们就记录黄点的最远点是紫点。

那么找到这个最远点有什么用呢？设黄点为结点 x，绿点为结点 y，那么有一个性质，就是在点 x（不含）到点 y 之间（不含）的所有点都不可能属于所有环的点集的交集。这个是显然的。因为肯定存在一个环，从紫点开始，依次经过环边来到黄点，然后再沿着非环边走到点 y。这样这个环完全没有经过 x 和 y 中间的点，因此它们就不是答案。

然而你发现对于每一个点你都跑一遍最远点，复杂度还是 \mathcal{O}(n^2) 的。但我们注意到这里可以优化：在 dfs 中，如果你访问到了一个之前就访问了的结点，则你可以直接对这个结点往后走的最大答案取 \max。这样每个点都只会被标记一次，复杂度就线性了。

然后就是区间打标记了。注意到我们在环上进行的操作，于是破环为链即可，这样就变成常规的差分操作了。

这里还有一个小问题：我们选出的点，不一定是合法的。因为考虑到可能存在一个环与我们选的环的点集交集为空，这个需要特判掉，所以你再用 Tarjan 找一遍环就可以了。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,all,a[500005],vis[500005],vis2[500005],fa[500005],wv[500005],zh[500005],in[500005],ollo[1000005],lol,chose;
int instk[500005],top;
vector<int>ve[500005],Ve;
bool find_huan(int x)//判环
{
    if(x == chose)return 0;//把答案点删了还有环，说明不合法
    vis[x] = instk[x] = 1;
    for(int i = 0;i < (int)ve[x].size();i ++)
    {
        int v = ve[x][i];
        if(v == chose)continue ;
        if(instk[v])//在栈中，则找到环
        {
            int p = x;
            while(p != v)
            {
                wv[++all] = p;
                in[p] = all;
                p = fa[p];
            }
            wv[++all] = v,in[v] = all,instk[x] = 0;
            return 1;
        }
        else if(!vis[v])
        {
            fa[v] = x;
            if(find_huan(v))
            {
                instk[x] = 0;
                return 1;
            }
        }
    }
    instk[x] = 0;
    return 0;
}
int get_dis(int x,int y)//两个点在环上的距离，x,y分别为环点下标
{
    if(x <= 0 || y <= 0)return -14587;
    if(x == y)return all;
    if(x < y)return y - x;
    return all - (x - y);
}
void dfs(int x)
{
    vis2[x] = 1;
    for(int i = 0;i < ve[x].size();i ++)
    {
        if(!in[ve[x][i]])//环外的点
        {
            if(!vis2[ve[x][i]])dfs(ve[x][i]);
            if(get_dis(lol,zh[ve[x][i]]) > get_dis(lol,zh[x]))zh[x] = zh[ve[x][i]];//已访问可直接继承
        }
        else//环内的点计算贡献
        {
            if(get_dis(lol,in[ve[x][i]]) > get_dis(lol,zh[x]))zh[x] = in[ve[x][i]];
        }
    }
}
void cha(int x,int y)//差分数组，注意x,y都不能取到
{
    if(x < y)ollo[x + 1] ++,ollo[y] --;
    else ollo[x + 1] ++,ollo[y + all] --;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++)
    {
        int u,v;
        cin >> u >> v;
        ve[u].push_back(v);
    }
    for(int i = 1;i <= n;i ++)
        if(!vis[i] && find_huan(i))break ;
    if(!all)//特判没有环的情况
    {
        cout << "NIE\n";
        return 0;
    }
    for(int i = 1;i <= n;i ++)vis[i] = fa[i] = instk[i] = 0;//注意到我们求得的环顺序是反的，交换一下顺序
    for(int i = 1;i <= all;i ++)in[wv[i]] = all - i + 1;
    for(int i = 1;i <= all / 2;i ++)swap(wv[i],wv[all - i + 1]);
    for(int i = 1;i <= all;i ++)
    {
        lol = i;
        dfs(wv[i]);
        cha(i,zh[wv[i]]);
    }
    for(int i = 1;i <= 2 * all;i ++)ollo[i] += ollo[i - 1];
    for(int i = 1;i <= all;i ++)
        if(ollo[i] + ollo[i + all] == 0)Ve.push_back(wv[i]);
    if(Ve.size())chose = Ve[0];//选取一个点
    for(int i = 1;i <= n;i ++)
        if(!vis[i] && find_huan(i))
        {
            cout << 0;
            return 0;
        }
    if(!Ve.size())cout << 0 << '\n';
    else
    {
        cout << Ve.size() << '\n';
        sort(Ve.begin(),Ve.end());
        for(int i = 0;i < Ve.size();i ++)cout << Ve[i] << " ";
    }
}