题目大意：给你一张有向图，问是否存在奇圈和偶圈
解题思路：二分图染色，如果染色成功，证明没有奇圈 给出大神的传送门
染色的时候，如果下一个点已经被染了，说明已经形成了一个圈了，那怎么判断是奇圈还是偶圈
首先，该点如果和下一个点的颜色不同，那么该圈就是偶圈了，反之，如果该点与下一点的颜色相同，该圈就是奇圈了
但是存在一种情况，两个奇圈合成了一个偶圈的，比如平行四边形加上一条对角线，，这张图就是奇圈和偶圈的结合了，那么现在的问题就是，怎么判断奇圈里面有偶圈了 如果两个奇圈存在公共点的话，那么这两个奇圈就可以组成一个偶圈了 证明：如果两个奇圈分别有a,b条边，两个圈存在一个公共点，令其有c条公共边，那么把他们合成一个环，环就有a + b – 2 * c条边了，可得，这是个偶圈(画个图就知道，平行四边形加上一条对角线)
Edge{int to, next;}E[M];int head[N], color[N], pre[N], belong[N];int n, m, tot;void AddEdge(int u, int v) {E[tot].to = v; E[tot].next = head[u]; head[u] = tot++;u = u ^ v; v = u ^ v; u = u ^ v;E[tot].to = v; E[tot].next = head[u]; head[u] = tot++;}void init() {memset(head, -1, sizeof(head));tot = 0;scanf(“%d%d”, &n, &m);int u, v;for (int i = 0; i < m; i++) {scanf(“%d%d”, &u, &v);AddEdge(u, v);}}bool odd, even;int cnt;void dfs(int u, int fa) {for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (v == fa) continue;if (color[v] == color[u]) {odd = true;++cnt;int t = v;while (!even) {if (belong[t]) {even = true;break;}belong[t] = cnt;t = pre[t];if (t == u || t == -1)break;}}if (color[v] == 3 – color[u]) even = true;if (!color[v]) {color[v] = 3 – color[u];pre[v] = u;dfs(v, u);}}}void solve() {memset(color, 0, sizeof(color));memset(belong, 0, sizeof(belong));cnt = 0;even = odd = false;for (int i = 1; i <= n; i++) {if (!color[i]) {color[i] = 1;pre[i] = -1;dfs(i, -1);}}printf(“%s\n”, odd ? “YES” : “NO”);printf(“%s\n”, even ? “YES” : “NO”);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
每个人心中，都会有一个古镇情怀，流水江南，烟笼人家。
