74/100
题意:
给出一个$n$个点,$m$条边的无向图,保证无自环和重边,要求你将所有边标上方向,且满足任意一条路径的长度不超过1。
题解:
首先不难想到,当图中包含奇环的时候,肯定不满足,因为至少会出现一条长度为2的路径,那么只有偶环或者无环的时候成立,那我们可以将所有的点视作两部分,变成一个二分图,二分图染色即可。
AC:
1 | const int N=2e5+5; |
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2021/06/22/CF-1144F/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!