【思维】图论+时间戳——Gym - 102501K 好题

这题非常好。。看似很简单其实比较复杂,交了一堆假算法全wa了。。

看题解也好久才弄明白

/*
给定一张有向图,确定一个点T,问有多少T0,满足所有T0->T的路径,都经过边(T0,T) 
建立反图,T变为起点,求所有T0,满足T->T0所有路径都经过(T,T0) 

首先确定用bfs,我们从每个和T连边T0的点开始bfs,vis[]数组记录每个点被访问的次数,如果T0被访问的次数=1,说明符合要求 
但是根据题意,我们要处理两个问题: 
    1.有形如T->T0->T1->T2->T0的边路径,此时T0任然满足要求,但是被访问了两次 
    2.根据1,我们如何判断T0第二次被访问时任是通过(T,T0)这天边的
解决方法:每个点u入队时维护一个pair<u,u的起始点src>,当我们访问到u时,将这个pair从queue取出
    此时如果u!=src,说明u是从别的源跑过来的,
    否则如果u==src,说明u本身就是源,如果vis[u]!=0,说明此时从u出发访问了一圈又回到了u,就不用再bfs下去,反之u这个源刚开始访问,要bfs下去 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define mk make_pair
vector<int>G[N];
int n,m,t,vis[N],f[N];

void bfs(int T){
    queue<pair<int,int> >q;
    for(auto v:G[T])
        q.push(mk(v,v));
    while(q.size()){
        int u=q.front().first,src=q.front().second;
        q.pop();
        /*
        这里为什么vis[u]>=3才continue?
        一个非初始点如果在一个环内,那么前两次访问可能是交给这个环的,当其他初始点需要从这个点切入环时,就要访问一次这个点
        所以vis[u]的上限要设为3(如果为2,那么其他s初始点就切不进来了) 
        */
        if(vis[u]>=3)continue;
        if(u!=src || u==src&&!vis[u])vis[u]++;//如果u!=其源点,那么随便怎么松弛都可以,如果u==其源点,那么不能再访问了 
        else continue;
        for(auto v:G[u])
            if(v!=T)q.push(mk(v,src));
    }
}

int main(){
    //freopen("hand01.in","r",stdin);
    cin>>n>>m>>t;t++;
    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        u++;v++;
        if(v==t)f[u]=1;
        G[v].push_back(u);
    }
    bfs(t);
    
    vector<int>ans;
    for(int i=1;i<=n;i++)
        if(f[i] && vis[i]<=1)ans.push_back(i);
    cout<<ans.size()<<'\n';
    for(auto x:ans)cout<<x-1<<"\n";
}

 

上一篇:Gym-101808I Ildar Yalalov


下一篇:Gym 101170A Arranging Hat dp