题解 AT4518 【[AGC032C] Three Circuits】

这道题我们可以从点的度数入手。 首先不难发现，由于所有点都在环上，所以需要每个点的度数都是偶数。则如果存在一个点的度数是奇数，则一定不合法。 那么这时候我们发现，由于每个点度数都是偶数，则图中一定存在一条欧拉回路，即所有点都在一个大环上。 由于这个题目中的环是可以拼接的，意思是，两个有公共点的环拼起来还是一个环，有了上面一条，可以将原问题变成：是否可以从一个大环中找出三个没有交的小环。 然后再考虑，如果存在一个点的度数 $\ge 6$，那么一定合法。考虑做欧拉回路的过程，每两次走到这个点，就可以分裂出一个环，则这个点就可以分裂出三个以上的环，那么随便选出三个之后，直接拼了剩下所有的边，就可以了。 然后考虑所有点的度数 $\leq 2$，加上连通的条件，那么所有点就连成了一个环。显然不符合题目条件。 这时候，剩下的情况就只剩下了若干个度数为 $4$ 和 $2$ 的点。 讨论度数为 $4$ 的点的个数： 一个点：画画图就能发现，只可能存在两个环套在一个点上的情况。这样只能弄出两个环，弄不出三个。 两个点：考虑这两个点连通的情况下，一定有至少两条不交的链，端点分别为这两个点。然后剩下的两条边就有了两种情况：一种是成了连接两个点的两条链（图一），一种是分别在两个点上挂两个环（图二）。不难发现，满足条件的只有图二。这个用一个 dfs，去掉度数为 $4$ 的两个点之后的四条链，有多少条链的两端原本连接的点是同一个点就能判断。   三个及以上的点：显然不论如何，都能分出至少 $3$ 个环。 那么经过上面的讨论，我们就可以判断出这个图能不能分成三个环了。 $\rm Code$： ```cpp template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; } #define ERROR return puts("No"), 0 #define OK return puts("Yes"), 0 const int MAXN = 100010; vector<int>to[MAXN]; int vis[MAXN]; int A, B; inline void dfs(int x) { vis[x] = 1; for(auto u : to[x]) if(vis[u] == 2) A ? B = u : A = u; else if(!vis[u]) dfs(u); } int main() { int n = ri, m = ri, mxd = 0, mxc = 0; for(int i = 1; i <= m; i++) { int u = ri, v = ri; to[u].push_back(v); to[v].push_back(u); } for(int i = 1; i <= n; i++) if(to[i].size() & 1) ERROR; else if(to[i].size() > mxd) mxd = to[i].size(), mxc = 1; else mxc += mxd == to[i].size(); if(mxd >= 6) OK; else if(mxd == 2 || mxc == 1) ERROR; else if(mxc > 2) OK; else { int cnt = 0; for(int i = 1; i <= n; i++) if(to[i].size() == 4) vis[i] = 2; for(int i = 1; i <= n; i++) if(!vis[i]) A = B = 0, dfs(i), cnt += A == B; puts(cnt ? "Yes" : "No"); } return 0; } ```