{"id":250,"date":"2019-02-06T17:25:00","date_gmt":"2019-02-06T09:25:00","guid":{"rendered":"https:\/\/www.caiqinyi.cn\/?p=250"},"modified":"2021-04-24T16:37:48","modified_gmt":"2021-04-24T08:37:48","slug":"union_find","status":"publish","type":"post","link":"https:\/\/www.caiqinyi.cn\/index.php\/2019\/02\/06\/union_find\/","title":{"rendered":"C++\u7248\u5e76\u67e5\u96c6"},"content":{"rendered":"<p>\u5927\u5e74\u521d\u4e00\u7684, \u590d\u4e60\u4e86\u4e00\u4e0b\u5e76\u67e5\u96c6, \u7528\u7684\u6559\u6750\u4e0a\u9762\u5199\u7684\u5e76\u67e5\u96c6\u5b9e\u9645\u4e0a\u7528\u8d77\u6765\u603b\u611f\u89c9\u5f88\u522b\u626d, \u6bd4\u5982\u7d22\u5f15\u4e0d\u662f\u4ece0\u5f00\u59cb, \u6ca1\u6709\u5bf9\u5904\u4e8e\u540c\u4e00\u96c6\u5408\u5185\u7684\u5143\u7d20\u4f5c\u5224\u65ad, \u4ee5\u53ca\u7528\u4e86\u6811\u4f5c\u4e3a\u5b58\u50a8\u96c6\u5408\u6839\u7ed3\u70b9\u7684\u6570\u636e\u7ed3\u6784, \u4e8e\u662f\u4fbf\u81ea\u5df1\u5199\u4e86\u4e2aC++\u7248\u7684.<\/p>\n<p><!--more--><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"C++\" data-enlighter-theme=\"monokai\">\r\nvector&lt;int&gt; parents;\r\nint find_mfset(int i,int j=0){\r\n    if(i&lt;0 || i&gt;parents.size()) return -1;\r\n    for(j=i;parents[j]&gt;=0;j=parents[j]);\r\n    return j;\r\n}\r\n\r\nvoid merge_mfset(int i,int j){\r\n    if (i&lt;0 || i&gt;parents.size() || j&lt;0 || j&gt;parents.size()) return;\r\n    int pi = find_mfset(i);\r\n    int pj = find_mfset(j);\r\n    if(pi==pj) return;\r\n    if (pi &gt; pj) {\r\n\t    parents[pj] += parents[pi];\r\n\t    parents[pi] = pj;\r\n    } \r\n    else {\r\n\t    parents[pi] += parents[pj];\r\n\t    parents[pj] = pi;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u5927\u5e74\u521d\u4e00\u7684, \u590d\u4e60\u4e86\u4e00\u4e0b\u5e76\u67e5\u96c6, \u7528\u7684\u6559\u6750\u4e0a\u9762\u5199\u7684\u5e76\u67e5\u96c6\u5b9e\u9645\u4e0a\u7528\u8d77\u6765\u603b\u611f\u89c9\u5f88\u522b\u626d, \u6bd4\u5982\u7d22\u5f15\u4e0d\u662f\u4ece0\u5f00\u59cb, \u6ca1 &hellip; <a href=\"https:\/\/www.caiqinyi.cn\/index.php\/2019\/02\/06\/union_find\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">C++\u7248\u5e76\u67e5\u96c6<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,7],"tags":[],"_links":{"self":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/250"}],"collection":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":4,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/250\/revisions"}],"predecessor-version":[{"id":786,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/250\/revisions\/786"}],"wp:attachment":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/media?parent=250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/categories?post=250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/tags?post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}