GYM102501 K. Birdwatching

题目链接:https://codeforces.com/gym/102501/problem/K

题目描述

一个有向图 P,一个关键点 T ,问有哪些点 S_i 经过 S_i \to T 可以到达点T ,而不经过边 S_i \to T 就无法到达点 T ?输出点的个数与编号。

边数点数 \leq 1e5

Solution

我们很容易能想到反向建图,将问题转化为:有哪些点 S_iT 不经过 T \to S_i 这条边就无法到达 S_i 的。(注意要求的基础上是原图存在 S_i \to T 这条边。

这样就将多起点问题转化成了单起点问题,以下讨论都发生在在反图中。

T 直接指向的点的集合为 D ,设 Q \in D\forall I \in DI \neq Q

若不存在一条路径使 Q 到达 I ,那么 Q 就记作答案。

正话反说,我们先将集合 D 直接视为答案集合 A ,如果存在一条路径使 Q 到达 I ,那么就将 Q 从答案集合 A 中删除。最后的 A 就是我们的所求。

在实际操作中,我们 令 Q 入队,它能走到哪个直接被 T 所指向的点(不包括 Q 自己) ,哪个点就不属于答案。

(有个小技巧是:从 Q 能走到哪个点(不包括 Q 自己),那么这个点就一定不是答案)

但是现在存在一个问题,如果我们使用通常的 一个点最多经过一次 的遍历法,显然是不对的。

pic3.png

(当 2 走向 3 后,3 被标记,4 便无法走向 3

而如果不加以限制一个点的最多通过次数 ,则会存在重复进队列、重复遍历从而无限循环。

经过摸索我们发现一个性质,就是一个点最多被遍历 2 次即可。

若点 OP 之间为双向边,点 P 为点 Q 为双向边。

那么 O 走到 P 之后,可以走向 P 所指向的除 O 以外的所有点,Q 也同理。

(这个除 O 以外就是上文所说的:Q 入队,它能走到哪个直接被 T 所指向的点(不包括 Q 自己) ,哪个点就不属于答案。,如果走回去 P 再走回 O ,不符合题目要求)

O 走向除 O 以外(P 所指向) 的点,Q 走向除 Q 以外(P 所指向) 的点。

有了这两个点,就相当于能走 P 所指向的所有点。

于是每个点最多被遍历 2 次,即可求出答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,t,cov[N];
vector<int> v[N];
set<int> s;
void init(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i = 1; i <= m ; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        v[y].push_back(x);
    }
}
void solve(){
    queue<pair<int,int> > q;
    for(auto e:v[t]) q.push(make_pair(e,e)),s.insert(e);
    cov[t]=4;
    while(!q.empty()){
        pair<int,int> p = q.front(); q.pop(); 
        int x = p.first, y = p.second;
        if( x != y ) {
            s.erase(x);
        }
        for(auto e:v[x]){
            if(cov[e]>=3) continue;
            cov[e]++;
            q.push(make_pair(e,y));
        }
    }
    printf("%d\n",s.size());
    for(auto e:s) printf("%d\n",e);
}
int main(){
    init();
    solve();
}
分类: 图论

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注