【CF1481D】AB Graph 题解
原题链接
题意简介
给你一个有向图。图中任意两点间都可以直接往来(含有 n*(n-1) 条边，无重边和自环)。每条边上有一个字母 a 或 b。现要求你找出一条长度为 m 的路径(可重复经过)，使路径上的字母构成的字符串为回文串。
思路分析
跟 C 题类似的分类讨论寻找方案。
首先，如果存在同一字母路径构成的环，那么只需要让路径全程都在这个环上就行了。
如果不满足上一条，表明任意两点间的两条有向边的字母不同。那么就有了下面的情形。
-
m 是 4 的倍数。那么只需要找到一个出边中有两种字母的点(如下图点2)，制造出 abba 或 baab 的循环就行了。
显然，n>2 时必然存在这样的点，不然必会形成同字母环，与“不满足第一条”相矛盾。
-
m 是奇数。那么随便找两个点走就行了，必然形成 ababa 或是 babab。
-
m 是 2 的倍数但不是 4 的倍数。找到一个出边有两种字母的点(还是那个点2)，然后从与之相连的另一个边开始(如点1)，先进行前面的循环，然后（进行中间循环）进入点2，再沿与进入点2的边字母相同的出边到达另一个点(点3)，然后在这两个点间进行后面的循环。
由上面的分析我们不难看出，唯一输出 No 的情形是 n=2 、没有同字母环且 m 是偶数的情形。
至于找环，我使用的是dfs序+栈的写法。
代码库
写得很丑，见谅。
#include
#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
inline int min(const int&a,const int&b){
return a