{"id":279,"date":"2024-03-29T10:25:35","date_gmt":"2024-03-29T02:25:35","guid":{"rendered":"https:\/\/solost.cn\/?p=279"},"modified":"2024-03-29T10:25:35","modified_gmt":"2024-03-29T02:25:35","slug":"414","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=279","title":{"rendered":"AcWing 860. \u67d3\u8272\u6cd5\u5224\u5b9a\u4e8c\u5206\u56fe"},"content":{"rendered":"<p><a href=\"[https:\/\/](https:\/\/www.acwing.com\/problem\/content\/862\/\">\u94fe\u63a5<\/a>)<\/p>\n<hr>\n<pre><code class=\"lang-cpp\">#include &lt;iostream&gt;\n#include &lt;cstring&gt;\n#include &lt;algorithm&gt;\n\nusing namespace std;\n\nconst int N = 100010 * 2;\nint e[N], ne[N], idx;\/\/\u90bb\u63a5\u8868\u5b58\u50a8\u56fe\nint h[N];\nint color[N];\/\/\u4fdd\u5b58\u5404\u4e2a\u70b9\u7684\u989c\u8272\uff0c0 \u672a\u67d3\u8272\uff0c1 \u662f\u7ea2\u8272\uff0c2 \u662f\u9ed1\u8272\nint n, m;\/\/\u70b9\u548c\u8fb9\n\nvoid add(int a, int b)\/\/\u90bb\u63a5\u8868\u63d2\u5165\u70b9\u548c\u8fb9\n{\n    e[idx] = b, ne[idx]= h[a], h[a] = idx++;\n}\n\nbool dfs(int u, int c)\/\/\u6df1\u5ea6\u4f18\u5148\u904d\u5386\n{\n    color[u] = c;\/\/u\u7684\u70b9\u6210 c \u67d3\u8272\n\n    \/\/\u904d\u5386\u548c u \u76f8\u90bb\u7684\u70b9\n    for(int i = h[u]; i!= -1; i = ne[i])\n    {\n        int b = e[i];             \n        if(!color[b])\/\/\u76f8\u90bb\u7684\u70b9\u6ca1\u6709\u989c\u8272,\u5219\u9012\u5f52\u5904\u7406\u8fd9\u4e2a\u76f8\u90bb\u70b9\n        {\n            if(!dfs(b, 3 - c)) return false;\/\/\uff083 - 1 = 2\uff0c \u5982\u679c u \u7684\u989c\u8272\u662f2\uff0c\u5219\u548c u \u76f8\u90bb\u7684\u67d3\u6210 1\uff09\n                                            \/\/\uff083 - 2 = 1\uff0c \u5982\u679c u \u7684\u989c\u8272\u662f1\uff0c\u5219\u548c u \u76f8\u90bb\u7684\u67d3\u6210 2\uff09\n        }\n        else if(color[b] &amp;&amp; color[b] != 3 - c)\/\/\u5982\u679c\u5df2\u7ecf\u67d3\u8272\uff0c\u5224\u65ad\u989c\u8272\u662f\u5426\u4e3a 3 - c\n        {                               \n            return false;\/\/\u5982\u679c\u4e0d\u662f\uff0c\u8bf4\u660e\u51b2\u7a81\uff0c\u8fd4\u56de             \n        }\n    }\n    return true;\n}\n\nint main()\n{\n    memset(h, -1, sizeof h);\/\/\u521d\u59cb\u5316\u90bb\u63a5\u8868\n    cin &gt;&gt; n &gt;&gt; m;\n    for(int i = 1; i &lt;= m; i++)\/\/\u8bfb\u5165\u8fb9\n    {\n        int a, b;\n        cin &gt;&gt; a &gt;&gt; b;\n        add(a, b), add(b, a);\n    }\n    for(int i = 1; i &lt;= n; i++)\/\/\u904d\u5386\u70b9\n    {\n        if(!color[i])\/\/\u5982\u679c\u6ca1\u67d3\u8272\n        {\n            if(!dfs(i, 1))\/\/\u67d3\u8272\u8be5\u70b9\uff0c\u5e76\u9012\u5f52\u5904\u7406\u548c\u5b83\u76f8\u90bb\u7684\u70b9\n            {\n                cout &lt;&lt; &quot;No&quot; &lt;&lt; endl;\/\/\u51fa\u73b0\u77db\u76fe\uff0c\u8f93\u51faNO \n                return 0;\n            }\n\n        }\n    }\n    cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;\/\/\u5168\u90e8\u67d3\u8272\u5b8c\u6210\uff0c\u6ca1\u6709\u77db\u76fe\uff0c\u8f93\u51faYES\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u94fe\u63a5) #include &lt;iostream&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; using namespace std; const int N = 100010 * 2; int e[N], ne[N], idx;\/\/\u90bb\u63a5\u8868\u5b58\u50a8\u56fe int h[N]; int color[N];\/\/\u4fdd\u5b58\u5404\u4e2a\u70b9\u7684\u989c\u8272\uff0c0 \u672a\u67d3\u8272\uff0c1 \u662f\u7ea2\u8272\uff0c2 \u662f\u9ed1\u8272 int n, m;\/\/\u70b9\u548c\u8fb9 void add(int a, int b)\/\/\u90bb\u63a5\u8868\u63d2\u5165\u70b9\u548c\u8fb9 { e[idx] = b, ne[idx]= h[a], h[a] = idx++; } bool dfs(int u, int c)\/\/\u6df1\u5ea6\u4f18\u5148\u904d\u5386 { color[u] = c;\/\/u\u7684\u70b9\u6210 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72,44],"tags":[65],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-acm","category-44","tag-65"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=279"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/279\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}