{"id":256,"date":"2026-08-28T23:40:06","date_gmt":"2026-08-28T15:40:06","guid":{"rendered":"https:\/\/huxiaole.cloud\/?p=256"},"modified":"2026-08-28T23:41:00","modified_gmt":"2026-08-28T15:41:00","slug":"cf1833e-round-dance","status":"publish","type":"post","link":"https:\/\/huxiaole.cloud\/index.php\/2026\/08\/28\/cf1833e-round-dance\/","title":{"rendered":"CF1833E Round Dance"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><a href=\"https:\/\/codeforces.com\/contest\/1833\/problem\/E\" target=\"_blank\" rel=\"noopener\">Problem &#8211; E &#8211; Codeforces<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u601d\u8def<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u6211\u4eec\u610f\u8bc6\u5230\u4e0d\u540c\u4f19\u4f34\u6070\u5982\u4e00\u4e2a\u8fb9\uff0c\u4eba\u5c31\u662f\u70b9\uff0c\u4e00\u4e2a\u5706\u5708\u821e\u4e2d\uff0c\u6bcf\u4e2a\u4eba\u7684\u5ea6\u90fd\u662f2<br>\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u5206\u6210\u4e24\u7c7b<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u95ed\u73af\uff1a\u6bcf\u4e2a\u70b9\u90fd\u6709\u4e24\u4e2a\u8fb9\uff0c\u8fd9\u6837\u5c31\u4e0d\u80fd\u63a5\u5165\u5176\u4ed6\u70b9\uff0c\u5fc5\u987b\u4f5c\u4e3a\u72ec\u7acb\u7684\u5706\u5708\u821e<\/li>\n\n\n\n<li>\u5f00\u94fe\uff1a\u94fe\u7684\u4e24\u7aef\u5ea6\u6570\u5747\u4e3a1\uff0c\u4ecd\u6709\u4e00\u4e2a\u7a7a\u95f2\u5ea6\u6570\u53ef\u4f9b\u8fde\u63a5<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\u6211\u4eec\u7edf\u8ba1\u95ed\u73af\u6570\u4e3a$cycle$\uff0c\u5f00\u94fe\u6570\u4e3a$path$<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6700\u5927\u6570\u91cf\uff1a$mx=cycle+path$\uff0c\u6211\u4eec\u5c06$path$\u9996\u5c3e\u76f8\u8fde<\/li>\n\n\n\n<li>\u6700\u5c0f\u6570\u91cf\uff1a$mi=cycle+(path > 1 ? 1 \uff1a 0)$\u5982\u679c\u6709$path$\u90a3\u4e48\u6211\u4eec\u5c31\u9996\u5c3e\u76f8\u8fde\uff0c\u6700\u7ec8\u53ea\u6709\u4e00\u4e2a\uff0c\u6ca1\u6709$path$\u5c31\u66f4\u597d\u4e86<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/Sunshine sunshine ladybugs awake,\n\n\/\/Clap your hooves and do a little shack.\n\n#include&lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\n  \n\nusing PII=pair&lt;int,int&gt;;\n\n  \n\nvoid solve(){\n\n&nbsp; &nbsp; int n;\n\n&nbsp; &nbsp; cin&gt;&gt;n;\n\n  \n\n&nbsp; &nbsp; vector&lt;PII&gt; edges;\n\n&nbsp; &nbsp; for(int u=1;u&lt;=n;u++){\n\n&nbsp; &nbsp; &nbsp; &nbsp; int v;\n\n&nbsp; &nbsp; &nbsp; &nbsp; cin&gt;&gt;v;\n\n&nbsp; &nbsp; &nbsp; &nbsp; edges.push_back({min(u,v),max(u,v)});\n\n&nbsp; &nbsp; }\n\n  \n\n&nbsp; &nbsp; sort(edges.begin(),edges.end());\n\n&nbsp; &nbsp; edges.erase(unique(edges.begin(),edges.end()),edges.end());\n\n  \n\n&nbsp; &nbsp; vector&lt;vector&lt;int&gt;&gt; g(n+1);\n\n&nbsp; &nbsp; for(auto &#91;u,v]:edges){\n\n&nbsp; &nbsp; &nbsp; &nbsp; g&#91;u].push_back(v);\n\n&nbsp; &nbsp; &nbsp; &nbsp; g&#91;v].push_back(u);\n\n&nbsp; &nbsp; }\n\n  \n\n&nbsp; &nbsp; vector&lt;bool&gt; vis(n+1,false);\n\n&nbsp; &nbsp; int cycle=0,path=0;\n\n  \n\n&nbsp; &nbsp; for(int i=1;i&lt;=n;i++){\n\n&nbsp; &nbsp; &nbsp; &nbsp; if(!vis&#91;i]){\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int point=0;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int degree=0;\n\n  \n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; queue&lt;int&gt; q;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.push(i);\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vis&#91;i]=true;\n\n  \n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(!q.empty()){\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int u=q.front();\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.pop();\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; point++;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; degree+=g&#91;u].size();\n\n  \n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(auto v:g&#91;u]){\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(!vis&#91;v]){\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vis&#91;v]=true;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.push(v);\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }\n\n  \n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int edges=degree\/2;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(point==edges){\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cycle++;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; path++;\n\n&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }\n\n&nbsp; &nbsp; &nbsp; &nbsp; }\n\n&nbsp; &nbsp; }\n\n  \n\n&nbsp; &nbsp; int mi=cycle+(path&gt;0?1:0);\n\n&nbsp; &nbsp; int mx=cycle+path;\n\n  \n\n&nbsp; &nbsp; cout&lt;&lt;mi&lt;&lt;\" \"&lt;&lt;mx&lt;&lt;endl;\n\n}\n\n  \n\nsigned main() {\n\n&nbsp; &nbsp; ios::sync_with_stdio(false);\n\n&nbsp; &nbsp; cin.tie(nullptr);\n\n&nbsp; &nbsp; int t;cin&gt;&gt;t;while(t--)\n\n&nbsp; &nbsp; solve();\n\n&nbsp; &nbsp; return 0;\n\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Problem &#8211; E &#8211; Codeforces \u601d\u8def \u6211\u4eec\u610f\u8bc6\u5230\u4e0d\u540c\u4f19\u4f34\u6070\u5982\u4e00\u4e2a\u8fb9\uff0c [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":115,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[20,12],"tags":[],"class_list":["post-256","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codeforces","category-12"],"_links":{"self":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/comments?post=256"}],"version-history":[{"count":2,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/256\/revisions"}],"predecessor-version":[{"id":259,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/256\/revisions\/259"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media\/115"}],"wp:attachment":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media?parent=256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/categories?post=256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/tags?post=256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}