{"id":180,"date":"2021-07-14T22:25:14","date_gmt":"2021-07-14T14:25:14","guid":{"rendered":"https:\/\/cirno.fun\/?p=180"},"modified":"2021-07-14T22:25:14","modified_gmt":"2021-07-14T14:25:14","slug":"%e7%ae%80%e8%bf%b0%e5%b9%b6%e6%9f%a5%e9%9b%86","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=180","title":{"rendered":"\u7b80\u8ff0\u5e76\u67e5\u96c6"},"content":{"rendered":"\n

\u5e76\u67e5\u96c6\u662f\u4e00\u79cd\u6811\u5f62\u7ed3\u6784\uff0c\u4e00\u822c\u60c5\u51b5\u4e0b\u5bf9N\u4e2a\u521d\u59cb\u72ec\u7acb\u7684\u5143\u7d20\u652f\u6301\u5408\u5e76\uff08\u5c06\u4e24\u4e2a\u5143\u7d20\u6240\u5728\u7684\u96c6\u5408\u5408\u5e76\uff09\u548c\u67e5\u8be2\uff08\u67e5\u8be2\u4e24\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\uff09\u4e24\u79cd\u64cd\u4f5c
<\/p>\n\n\n

\u8fd9\u91cc\u501f\u7528\u6d1b\u8c37\u7684P3367<\/a>\u6765\u7406\u89e3\u5176\u4f5c\u7528\u66f4\u597d
\u6284\u4e00\u4e0b\u9898\u9762\uff1a<\/p>\n\n\n

\"\"<\/figure>\n\n\n

\u7406\u89e3\u4f5c\u7528\u4e4b\u540e\u6765\u770b\u5b9e\u73b0\uff1a
\u6211\u4eec\u9700\u8981\u4e00\u4e2a\u6570\u7ec4 fa[] \u6765\u50a8\u5b58\u6bcf\u4e2a\u5143\u7d20\u7684\u5927\u54e5\uff0c\u5728\u521d\u59cb\u60c5\u51b5\u4e0b\uff0c\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u72ec\u7acb\u7684\u4e00\u4e2a\u96c6\u5408\uff0c\u6240\u4ee5\u5927\u54e5\u5c31\u662f\u81ea\u5df1\u3002\u5982\u679c\u4e24\u4e2a\u5143\u7d20\u7684\u5927\u54e5\u76f8\u540c\uff0c\u6216\u8005\u5927\u5927\u54e5\u3001\u5927\u5927\u5927\u54e5\u7b49\u5411\u4e0a\u53ef\u4ee5\u8ffd\u6eaf\u5230\u516c\u5171\u7684\u9886\u5bfc\uff0c\u5219\u8fd9\u4e24\u4e2a\u5143\u7d20\u5904\u4e8e\u4e00\u4e2a\u96c6\u5408\uff0c\u53cd\u4e4b\u4e0d\u662f

\u770b\u4e00\u4e2a\u56fe<\/p>\n\n\n

\"\"<\/figure>\n\n\n

\u5982\u4e0a\u56fe\u6240\u793a\uff0cx\u548c2\u62e5\u6709\u5171\u540c\u7684\u5927\u54e51\uff0c\u6240\u4ee5x\u548c2\u5c5e\u4e8e\u4e00\u4e2a\u96c6\u5408\uff0c\u4f46\u662fx\u548c345\u7ed3\u70b9\u867d\u7136\u6ca1\u6709\u5171\u540c\u7684 \u5927\u54e5 \uff0c\u4f46\u662f\u8fd8\u6709\u5171\u540c\u7684\u7956\u51481\uff0c\u8fd9\u662f\u4ed6\u4eec\u4ecd\u5c5e\u4e8e\u4e00\u4e2a\u96c6\u5408\uff08\u867d\u7136\u770b\u8d77\u6765\u50cf\u662f\u5e9f\u8bdd\uff0c\u4f46\u662f\u5f88\u91cd\u8981\uff09\u3002\u4e0a\u56fe\u4e2d\u5171\u6709\u4e24\u4e2a\u96c6\u5408
\u5bf9\u4e8e\u4e00\u4e2a\u8282\u70b9\u7684\u7956\u5148\u67e5\u8be2\uff0c\u53ef\u4ee5\u7528\u9012\u5f52\u6216\u8005\u5faa\u73af\u89e3\u51b3\uff0c\u601d\u8def\u662f\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u7684\u5927\u54e5\u4e0d\u662f\u81ea\u5df1\uff0c\u5c31\u627e\u4ed6\u7684\u5927\u54e5\uff0c\u770b\u4ed6\u7684\u5927\u54e5\u7684\u7956\u5148\u662f\u4e0d\u662f\u81ea\u5df1<\/p>\n\n\n

int find(int x){\/\/\u67e5\u8be2x\u7684\u5927\u54e5\n     if(fa[x]==x)    return x;    \/\/\u5982\u679c\u7956\u5148\u662f\u81ea\u5df1\uff0c\u5219\u4ed6\u662f\u6b64\u96c6\u5408\u7684\u6811\u7684\u6839\u8282\u70b9\n     else return find(fa[x]);     \/\/\u5982\u679c\u4e0d\u662f\uff0c\u5411\u4e0a\u627e\u4e00\u5c42\uff0c\u770b\u4ed6\u7684\u7236\u8282\u70b9\n     \/\/else return fa[x]=find(fa[x]);\n}<\/code><\/pre>\n\n\n
\u5bf9\u4e0e\u5408\u5e76\u7684\u64cd\u4f5c\uff0c\u9700\u8981\u6ce8\u610f\u7684\u662f\u5408\u5e76x\uff0cy\u4e24\u4e2a\u5143\u7d20\u65f6\u5019\u6307\u7684\u662f\u6240\u5728\u7684\u96c6\u5408\uff0c\u5982\u4e0a\u56fe\u4e2d\u5408\u5e765\u548cd\u8282\u70b9\uff0c\u5c31\u4f1a\u4f7f\u5f97\u6240\u6709\u70b9\u5f52\u4e8e\u540c\u4e00\u4e2a\u96c6\u5408\u3002\u6240\u4ee5\uff0c\u6211\u4eec\u4f7f\u7528\u64d2\u8d3c\u5148\u64d2\u738b\u7684\u601d\u60f3\uff0c\u5408\u5e76\u4e24\u4e2a\u56e2\u4f19AB\uff0c\u5c31\u662f\u8ba9A\u56e2\u4f19\u7684\u5927\u54e5\u52a0\u5165\u5230B\u56e2\u4f19\u5f53\u5c0f\u5f1f\uff0c\u8fd9\u6837\u4ed6\u7684\u5c0f\u5f1f\u4e5f\u8ddf\u7740\u4ed6\u5f52\u987aB\u56e2\u4f19\u4e86<\/p>\n\n\n
void merge(int a,int b){\n     \/\/\u5408\u5e76ab\n     int f1=find(a),f2=find(b);\n     fa[f1]=f2;\n     \/\/\u8ba9A\u56e2\u4f19\u7684\u5927\u54e5\u5f52\u987aB\u56e2\u4f19\u548c\u53cd\u4e4b\u6ca1\u6709\u533a\u522b\uff0c\u6211\u4eec\u53ea\u5173\u5fc3\u4e24\u4e2a\u4eba\u662f\u5426\u5728\u4e00\u4e2a\u56e2\u4f19\uff0c\u4e0d\u5173\u5fc3\u4e0a\u4e0b\u7ea7\u5173\u7cfb\n } <\/code><\/pre>\n\n\n
\u8fd9\u6837\u4ee5\u6765\uff0c\u5c31\u5b9e\u73b0\u4e86\u5e76\u67e5\u96c6\u7684\u529f\u80fd
\u73b0\u5728\u6709\u4e00\u4e2a\u4e25\u91cd\u7684\u95ee\u9898\uff0c\u6211\u4eec\u7684find\u51fd\u6570\u5728\u6811\u4e2d\u6309\u7167\u4e00\u7ea7\u4e00\u7ea7\u5411\u4e0a\u7684\u987a\u5e8f\u67e5\u627e\uff0c\u5728\u7c7b\u7ebf\u6027\u7ed3\u6784\u4e2d\u7684\u8868\u73b0\u4f1a\u53ca\u5176\u5dee\u52b2\uff0c\u5982
1-2-3-4-5-6-7-8-9-10-11-12
\u5047\u8bbe1\u662f\u6839\u8282\u70b9\uff0c\u8fd9\u91cc\u6709\u4ed6\u768412\u4ee3\u5b50\u5b59\uff0c\u5219\u6bcf\u6b21find(12)\u65f6\u90fd\u9700\u8981\u5411\u4e0a\u8d7011\u5c42\uff0c\u6548\u7387\u5f88\u4f4e\u800c\u4e14\u6ca1\u6709\u5fc5\u8981\uff0c\u5e76\u67e5\u96c6\u53ea\u5173\u5fc3\u4e24\u4e2a\u5143\u7d20\u96c6\u5408\u7684\u662f\/\u5426\u5173\u7cfb\uff0c\u4e0d\u5173\u5fc3\u5c42\u7ea7\uff0c\u6240\u4ee5\u6211\u4eec\u4e00\u822c\u90fd\u4f1a\u4f7f\u7528\u8def\u5f84\u538b\u7f29\uff0c\u5982\u679c\u67e5\u5230\u4e8612\u7b49\u4eba\u7684\u5927\u54e5\u662f1\uff0c\u5c31\u76f4\u63a5\u8ba912\u7b49\u53d8\u62101\u7684\u76f4\u63a5\u4e0b\u7ea7
\u7528\u4ee3\u7801\u5b9e\u73b0\u5c31\u662ffind\u51fd\u6570\u4e2d\u6ce8\u91ca\u7684\u90e8\u5206\uff0c\u5f88\u7b80\u5355

<\/p>\n\n\n
\"\"
\u6211\u4eec\u4e0d\u5173\u5fc3\u5c42\u7ea7\u5173\u7cfb\uff0c\u4e3a\u4e86\u6548\u7387\u6240\u4ee5\u5e0c\u671b\u6811\u8d8a\u6d45\u8d8a\u597d<\/figcaption><\/figure>\n\n\n
\u6700\u540e\u8d34\u4e0a\u5b8c\u6574\u7684\u4ee3\u7801<\/p>\n\n\n
\/\/P3367\u3010\u6a21\u677f\u3011\u5e76\u67e5\u96c6\n include<bits\/stdc++.h>\n using namespace std;\n\n const int MAXN=500000;\n int fa[MAXN];\n\n inline void init(){ \/\/\u521d\u59cb\u5316\u65f6\u6bcf\u4e2a\u4eba\u90fd\u662f\u72ec\u7acb\u7684\n     for(int i=0;i<MAXN;i++)\n         fa[i]=i;\n }\n\n int find(int x){\n     if(fa[x]==x)    return x;\n     else return fa[x]=find(fa[x]);\n }\n\n int main(){\n     init();\n\n     int n,m;\n     scanf(\"%d%d\",&n,&m);\n\n     int opt,x,y,f1,f2;\n     for(int i=1;i<=m;i++){\/\/\u8fd9\u91cc\u4e3a\u4e86\u65b9\u4fbf\u6ca1\u6709\u518d\u5199\u6210\u51fd\u6570\n         scanf(\"%d%d%d\",&opt,&x,&y);\n         f1=find(x),f2=find(y);\n         if(opt==1)\n             fa[f1]=f2;\n         else if(f1==f2) puts(\"Y\");\n         else puts(\"N\");\n     }\n     return 0;\n }<\/code><\/pre>\n\n\n
\u5e76\u67e5\u96c6\u662f\u4e00\u4e2a\u5341\u5206\u5f3a\u5927\u4e14\u597d\u7528\u7684\u7b97\u6cd5\uff0c\u5728\u5173\u4e8e\u56fe\u7684\u8fde\u901a\u6027\u95ee\u9898\u4e0a\u5f80\u5f80\u53ef\u4ee5\u53d1\u6325\u5de8\u5927\u7684\u4f5c\u7528\uff0c\u4e00\u4e2a\u5178\u578b\u7684\u4f8b\u5b50\u5c31\u662fKruscal\u6700\u5c0f\u751f\u6210\u6811\u3002\u4f46\u662f\u4ed6\u540c\u65f6\u6709\u7740\u53ea\u5408\u4e0d\u5206\u7684\u81f4\u547d\u7f3a\u70b9\uff0c\u5982\u679c\u9700\u8981\u62c6\u5206\u5219\u4e0d\u80fd\u8003\u8651\u7528\u5e76\u67e5\u96c6\u7ef4\u62a4<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5e76\u67e5\u96c6\u662f\u4e00\u79cd\u6811\u5f62\u7ed3\u6784\uff0c\u4e00\u822c\u60c5\u51b5\u4e0b\u5bf9N\u4e2a\u521d\u59cb\u72ec\u7acb\u7684\u5143\u7d20\u652f\u6301\u5408\u5e76\uff08\u5c06\u4e24\u4e2a\u5143\u7d20\u6240\u5728\u7684\u96c6 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,13],"tags":[],"class_list":["post-180","post","type-post","status-publish","format-standard","hentry","category-2","category-13"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=180"}],"version-history":[{"count":0,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/180\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}