题解：CF1361E James and the Chase

题意

给定一个

n

个点

m

条边强连通分量，如果我们认为点

x

是有趣的，那么对于任意的

i \in [1,n]

，都有保证

x

到

i

有且仅有一条简单路径。

求出所有有趣的点的编号。若有趣的点数小于

0.2 \times n

，输出 -1。

多测。

1 \leq n \leq 10^5,1 \leq m \leq 2 \times 10^5

。

题解

首先我们考虑怎么判断一个有趣的点。可以发现令这个点为根建出叶向 DFS 树，那么这棵树上不能存在横叉边或者前向边，只能存在返祖边，那么这个点是有趣的。

其次考虑如何找到一个有趣的点。由于有限制若有趣的点数小于

0.2 \times n

，输出 -1，那么我们可以随机跑

100

次，每次随机一个点

O(n+m)

判断这个点是否是有趣的。随机

100

次出现错误的概率为

0.2^{100}

，大概为

1.27 \times 10^{-70}

，因此出错概率极低。

然后考虑如果找到了一个有趣的点，如何找到其它的所有有趣的点。考虑到这个叶向 DFS 树实际上有很好的性质，因为它只有返祖边。然后观察结构：

如果一个点被两个及以上返祖边覆盖，那么这个点一定不是有趣的，因为它到根一定有至少两条简单路径。因此这个点一定被有且仅有一条返祖边覆盖。
设这个点为 $x$ ，这条覆盖点的返祖边到达的“祖先”是有趣的，那么点 $x$ 就是有趣的。

这启示我们找到所有的“有且仅有一条返祖边覆盖”的点集

S

（这个可以用树上差分实现），并且对于里面的每一个元素都找到这个点被覆盖的返祖边的祖先节点，在建出的 DFS 树上从上往下 dp 即可。

CPP

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=2e5+5,inf=2e9;
mt19937 Rand(time(0));
int TestCase,n,m,tot[maxn],dep[maxn],low[maxn],rt;
bool lian[maxn],vis[maxn],good[maxn];
vector<int> G[maxn],T[maxn];
void init(){
    rt=0;
    for(int i=1;i<=n;i++){
        dep[i]=inf;
        tot[i]=low[i]=lian[i]=vis[i]=good[i]=0;
        G[i].clear();T[i].clear();
    }
}
bool getchk(int x){
    lian[x]=true;vis[x]=true;
    for(auto v:G[x]){
        if(vis[v] && !lian[v])return true;
        if(vis[v])continue;
        if(getchk(v))return true;
    }
    lian[x]=false;
    return false;
}
int getrt(){
    for(int i=1;i<=100;i++){
        for(int j=1;j<=n;j++)lian[j]=vis[j]=false;
        int u=Rand()%n+1;
        if(!getchk(u))return u;
    }
    return -1;
}
void getdep(int x,int f){
    dep[x]=dep[f]+1;low[x]=x;
    for(auto v:G[x]){
        if(dep[v]<dep[x]){
            tot[v]--;tot[x]++;
            if(dep[v]<dep[low[x]])low[x]=v;
        }else{
            T[x].push_back(v);
            getdep(v,x);
            if(dep[low[v]]<dep[low[x]])low[x]=low[v];
        } 
    }
}
void gettot(int x){
    for(auto v:T[x]){
        gettot(v);
        tot[x]+=tot[v];
    }
}
void getdp(int x){
    if(x!=rt && tot[x]==1 && good[low[x]])good[x]=true;
    for(auto v:T[x])getdp(v);
}
void solve(){
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        G[x].push_back(y);
    }
    rt=getrt();
    if(rt==-1){
        cout<<"-1\n";
        return;
    }
    good[rt]=true;
    getdep(rt,0);
    gettot(rt);getdp(rt);
    int ans=0;
    for(int i=1;i<=n;i++)ans+=((int)good[i]);
    if(ans*5<n){
        cout<<"-1\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(good[i])cout<<i<<" ";
    }
    cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>TestCase;
    while(TestCase--)solve();
    return 0;
}

题解：CF1361E James and the Chase

文章操作

题意

题解

相关推荐

评论

题解：CF1361E James and the Chase