{"id":73,"date":"2023-03-15T22:17:48","date_gmt":"2023-03-15T14:17:48","guid":{"rendered":"https:\/\/solost.cn\/?p=73"},"modified":"2023-03-15T22:17:48","modified_gmt":"2023-03-15T14:17:48","slug":"163","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=73","title":{"rendered":"\u5e76\u67e5\u96c6"},"content":{"rendered":"<pre><code class=\"lang-cpp\">(1)\u6734\u7d20\u5e76\u67e5\u96c6\uff1a\n\n    int p[N]; \/\/\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x) p[x] = find(p[x]);\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i &lt;= n; i ++ ) p[i] = i;\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    p[find(a)] = find(b);\n\n\n(2)\u7ef4\u62a4size\u7684\u5e76\u67e5\u96c6\uff1a\n\n    int p[N], size[N];\n    \/\/p[]\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9, size[]\u53ea\u6709\u7956\u5b97\u8282\u70b9\u7684\u6709\u610f\u4e49\uff0c\u8868\u793a\u7956\u5b97\u8282\u70b9\u6240\u5728\u96c6\u5408\u4e2d\u7684\u70b9\u7684\u6570\u91cf\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x) p[x] = find(p[x]);\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i &lt;= n; i ++ )\n    {\n        p[i] = i;\n        size[i] = 1;\n    }\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    size[find(b)] += size[find(a)];\n    p[find(a)] = find(b);\n\n\n(3)\u7ef4\u62a4\u5230\u7956\u5b97\u8282\u70b9\u8ddd\u79bb\u7684\u5e76\u67e5\u96c6\uff1a\n\n    int p[N], d[N];\n    \/\/p[]\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9, d[x]\u5b58\u50a8x\u5230p[x]\u7684\u8ddd\u79bb\n\n    \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9\n    int find(int x)\n    {\n        if (p[x] != x)\n        {\n            int u = find(p[x]);\n            d[x] += d[p[x]];\n            p[x] = u;\n        }\n        return p[x];\n    }\n\n    \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n\n    for (int i = 1; i &lt;= n; i ++ )\n    {\n        p[i] = i;\n        d[i] = 0;\n    }\n\n    \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a\n    p[find(a)] = find(b);\n    d[find(a)] = distance; \/\/ \u6839\u636e\u5177\u4f53\u95ee\u9898\uff0c\u521d\u59cb\u5316find(a)\u7684\u504f\u79fb\u91cf\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>(1)\u6734\u7d20\u5e76\u67e5\u96c6\uff1a int p[N]; \/\/\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9 \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } \/\/ \u521d\u59cb\u5316\uff0c\u5047\u5b9a\u8282\u70b9\u7f16\u53f7\u662f1~n for (int i = 1; i &lt;= n; i ++ ) p[i] = i; \/\/ \u5408\u5e76a\u548cb\u6240\u5728\u7684\u4e24\u4e2a\u96c6\u5408\uff1a p[find(a)] = find(b); (2)\u7ef4\u62a4size\u7684\u5e76\u67e5\u96c6\uff1a int p[N], size[N]; \/\/p[]\u5b58\u50a8\u6bcf\u4e2a\u70b9\u7684\u7956\u5b97\u8282\u70b9, size[]\u53ea\u6709\u7956\u5b97\u8282\u70b9\u7684\u6709\u610f\u4e49\uff0c\u8868\u793a\u7956\u5b97\u8282\u70b9\u6240\u5728\u96c6\u5408\u4e2d\u7684\u70b9\u7684\u6570\u91cf \/\/ \u8fd4\u56dex\u7684\u7956\u5b97\u8282\u70b9 int find(int x) { if (p[x] [&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],"tags":[],"class_list":["post-73","post","type-post","status-publish","format-standard","hentry","category-acm"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/73","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=73"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/73\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=73"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=73"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=73"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}