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_i 是 T 不经过 T \to S_i 这条边就无法到达 S_i 的。（注意要求的基础上是原图存在 S_i \to T 这条边。

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

令 T 直接指向的点的集合为 D ，设 Q \in D ，\forall I \in D 且 I \neq Q 。

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

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

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

（有个小技巧是：从 Q 能走到哪个点（不包括 Q 自己），那么这个点就一定不是答案）

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

（当 2 走向 3 后，3 被标记，4 便无法走向 3 ）

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

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

若点 O 与 P 之间为双向边，点 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();
}