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();
}
0 条评论