RainAir
My OI Blog
RainAir
AGC027C - ABland Yard

题目描述

题目链接
给出一个 $N$ 个点、 $M$ 条边的无向图(节点编号 $1~N$ )。每个节点有一个值 A 或 B,你可以从任意一个节点出发,经过一些节点后(可以重复经过),你将经过的节点的值顺次写出来,就可以得到一个只包含 A 或 B 的字符串。求对于只包含 A 或 B 的字符串 $S$ 都找得到一个合法的访问序列使得得到的字符串恰好为 $S$ 。

题解

显然如果存在一个类似于 AABB 的环就可以满足所有的条件。于是题目变成了判断图里有没有这样的环。
这个结论证明很好证明:如果这个环里 A 或 B 的个数小于1,那么无法构成 AA 或 BB。
如果这个环里连续 A 或 B 的个数超过 2,则存在一个结尾为 ABBA 或 BAAB 无法构成。
我们判断可以类比拓扑排序的方法,将所有只与 A 或 B 相连的点删除,不断进行知道不能删除为止。
剩下的就一定是形如 AABB 的环了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/284
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

AGC027C - ABland Yard
题目描述 题目链接 给出一个 $N$ 个点、 $M$ 条边的无向图(节点编号 $1~N$ )。每个节点有一个值 A 或 B,你可以从任意一个节点出发,经过一些节点后(可以重复经过),你将经过的节点…
扫描二维码继续阅读
2018-11-22
标签
近期评论