{"id":486,"date":"2022-04-14T20:09:53","date_gmt":"2022-04-14T12:09:53","guid":{"rendered":"http:\/\/120.55.184.7\/?p=486"},"modified":"2025-04-27T17:59:04","modified_gmt":"2025-04-27T09:59:04","slug":"%e5%b9%b6%e6%9f%a5%e9%9b%86","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=486","title":{"rendered":"\u5e76\u67e5\u96c6"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u4ec0\u4e48\u662f\u5e76\u67e5\u96c6\uff1f<\/h2>\n\n\n\n<p>\u5e76\u67e5\u96c6(Union-Find)\u662f\u4e00\u79cd\u6811\u578b\u7684\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5904\u7406\u4e00\u4e9b<strong>\u4e0d\u76f8\u4ea4\u96c6\u5408<\/strong>\u7684\u5408\u5e76(Union)\u53ca\u67e5\u8be2(Find)\u95ee\u9898\u3002\u5b83\u652f\u6301\u4ee5\u4e0b\u4e24\u79cd\u57fa\u672c\u64cd\u4f5c\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u67e5\u627e(Find)<\/strong>\uff1a\u786e\u5b9a\u5143\u7d20\u5c5e\u4e8e\u54ea\u4e2a\u5b50\u96c6<\/li>\n\n\n\n<li><strong>\u5408\u5e76(Union)<\/strong>\uff1a\u5c06\u4e24\u4e2a\u5b50\u96c6\u5408\u5e76\u4e3a\u4e00\u4e2a\u96c6\u5408<\/li>\n<\/ol>\n\n\n\n<p>\u5e76\u67e5\u96c6\u5728\u8ba1\u7b97\u673a\u79d1\u5b66\u4e2d\u6709\u5e7f\u6cdb\u5e94\u7528\uff0c\u5982\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u56fe\u7684\u8fde\u901a\u5206\u91cf\u8ba1\u7b97<\/li>\n\n\n\n<li>Kruskal\u6700\u5c0f\u751f\u6210\u6811\u7b97\u6cd5<\/li>\n\n\n\n<li>\u7f51\u7edc\u8fde\u63a5\u95ee\u9898<\/li>\n\n\n\n<li>\u793e\u4ea4\u7f51\u7edc\u4e2d\u7684\u670b\u53cb\u5708\u8ba1\u7b97<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u5e76\u67e5\u96c6\u7684\u57fa\u672c\u5b9e\u73b0<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u6570\u636e\u7ed3\u6784\u8868\u793a<\/h3>\n\n\n\n<p>\u5728Golang\u4e2d\uff0c\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u4e00\u4e2a\u6570\u7ec4(parent)\u6765\u8868\u793a\u5e76\u67e5\u96c6\u7684\u68ee\u6797\u7ed3\u6784\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\ntype UnionFind struct {\n    parent &#x5B;]int\n    count  int \/\/ \u8fde\u901a\u5206\u91cf\u4e2a\u6570\n}\n<\/pre><\/div>\n\n\n<p>\u521d\u59cb\u5316\u65f6\uff0c\u6bcf\u4e2a\u5143\u7d20\u7684\u7236\u8282\u70b9\u90fd\u662f\u81ea\u5df1\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nfunc NewUnionFind(n int) *UnionFind {\n    uf := &amp;UnionFind{\n        parent: make(&#x5B;]int, n),\n        count:  n,\n    }\n    for i := 0; i &lt; n; i++ {\n        uf.parent&#x5B;i] = i\n    }\n    return uf\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">\u67e5\u627e\u64cd\u4f5c(Find)<\/h3>\n\n\n\n<p>\u67e5\u627e\u5143\u7d20\u6240\u5728\u96c6\u5408\u7684\u6839\u8282\u70b9\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nfunc (uf *UnionFind) Find(x int) int {\n    for uf.parent&#x5B;x] != x {\n        x = uf.parent&#x5B;x]\n    }\n    return x\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">\u5408\u5e76\u64cd\u4f5c(Union)<\/h3>\n\n\n\n<p>\u5c06\u4e24\u4e2a\u5143\u7d20\u6240\u5728\u7684\u96c6\u5408\u5408\u5e76\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: plain; title: ; notranslate\" title=\"\">\nfunc (uf *UnionFind) Union(x, y int) {\n    rootX := uf.Find(x)\n    rootY := uf.Find(y)\n    if rootX == rootY {\n        return\n    }\n    uf.parent&#x5B;rootX] = rootY\n    uf.count--\n}\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">\u4f18\u5316\u6280\u672f<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. \u8def\u5f84\u538b\u7f29(Path Compression)<\/h3>\n\n\n\n<p>\u5728\u67e5\u627e\u8fc7\u7a0b\u4e2d\uff0c\u5c06\u8def\u5f84\u4e0a\u7684\u6240\u6709\u8282\u70b9\u76f4\u63a5\u8fde\u63a5\u5230\u6839\u8282\u70b9\uff0c\u51cf\u5c11\u540e\u7eed\u67e5\u627e\u7684\u6df1\u5ea6\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nfunc (uf *UnionFind) Find(x int) int {\n    if uf.parent&#x5B;x] != x {\n        uf.parent&#x5B;x] = uf.Find(uf.parent&#x5B;x]) \/\/ \u8def\u5f84\u538b\u7f29\n    }\n    return uf.parent&#x5B;x]\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">2. \u6309\u79e9\u5408\u5e76(Union by Rank)<\/h3>\n\n\n\n<p>\u7ef4\u62a4\u4e00\u4e2arank\u6570\u7ec4\u8bb0\u5f55\u6bcf\u68f5\u6811\u7684\u9ad8\u5ea6\uff0c\u5408\u5e76\u65f6\u5c06\u8f83\u77ee\u7684\u6811\u5408\u5e76\u5230\u8f83\u9ad8\u7684\u6811\u4e0b\uff1a<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\ntype UnionFind struct {\n    parent &#x5B;]int\n    rank   &#x5B;]int\n    count  int\n}\n\nfunc NewUnionFind(n int) *UnionFind {\n    uf := &amp;UnionFind{\n        parent: make(&#x5B;]int, n),\n        rank:   make(&#x5B;]int, n),\n        count:  n,\n    }\n    for i := 0; i &lt; n; i++ {\n        uf.parent&#x5B;i] = i\n        uf.rank&#x5B;i] = 1\n    }\n    return uf\n}\n\nfunc (uf *UnionFind) Union(x, y int) {\n    rootX := uf.Find(x)\n    rootY := uf.Find(y)\n    if rootX == rootY {\n        return\n    }\n    \/\/ \u6309\u79e9\u5408\u5e76\n    if uf.rank&#x5B;rootX] &gt; uf.rank&#x5B;rootY] {\n        uf.parent&#x5B;rootY] = rootX\n    } else if uf.rank&#x5B;rootX] &lt; uf.rank&#x5B;rootY] {\n        uf.parent&#x5B;rootX] = rootY\n    } else {\n        uf.parent&#x5B;rootY] = rootX\n        uf.rank&#x5B;rootX]++\n    }\n    uf.count--\n}\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">\u5f00\u6e90\u5b9e\u73b0\u5206\u6790<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. github.com\/yourbasic\/uf<\/h3>\n\n\n\n<p>\u8fd9\u662f\u4e00\u4e2a\u7b80\u6d01\u9ad8\u6548\u7684Golang\u5e76\u67e5\u96c6\u5b9e\u73b0\uff0c\u7279\u70b9\u5305\u62ec\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u4f7f\u7528\u8def\u5f84\u538b\u7f29\u4f18\u5316<\/li>\n\n\n\n<li>\u63a5\u53e3\u7b80\u6d01\u660e\u4e86<\/li>\n\n\n\n<li>\u652f\u6301\u52a8\u6001\u6269\u5bb9<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\n\/\/ \u521b\u5efa\u5305\u542bn\u4e2a\u5143\u7d20\u7684\u5e76\u67e5\u96c6\nuf := uf.New(n)\n\n\/\/ \u5408\u5e76\u4e24\u4e2a\u5143\u7d20\nuf.Union(a, b)\n\n\/\/ \u67e5\u627e\u5143\u7d20\u6240\u5c5e\u96c6\u5408\nroot := uf.Find(a)\n\n\/\/ \u83b7\u53d6\u8fde\u901a\u5206\u91cf\u6570\u91cf\ncount := uf.Count()\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">2. github.com\/kelvinlau\/go-unionfind<\/h3>\n\n\n\n<p>\u8fd9\u4e2a\u5b9e\u73b0\u63d0\u4f9b\u4e86\u66f4\u591a\u529f\u80fd\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u652f\u6301\u6309\u5927\u5c0f\u5408\u5e76(Union by Size)<\/li>\n\n\n\n<li>\u63d0\u4f9bConnected\u65b9\u6cd5\u68c0\u67e5\u8fde\u901a\u6027<\/li>\n\n\n\n<li>\u652f\u6301\u91cd\u7f6e\u5e76\u67e5\u96c6<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nuf := unionfind.New(n)\nuf.Union(a, b)\nif uf.Connected(a, b) {\n    fmt.Println(&quot;a and b are connected&quot;)\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">3. github.com\/wangzheng0822\/algo<\/h3>\n\n\n\n<p>\u8fd9\u4e2a\u7b97\u6cd5\u5e93\u4e2d\u7684\u5e76\u67e5\u96c6\u5b9e\u73b0\u7279\u70b9\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u540c\u65f6\u4f7f\u7528\u8def\u5f84\u538b\u7f29\u548c\u6309\u79e9\u5408\u5e76<\/li>\n\n\n\n<li>\u63d0\u4f9b\u8be6\u7ec6\u7684\u6587\u6863\u548c\u793a\u4f8b<\/li>\n\n\n\n<li>\u652f\u6301\u6cdb\u578b\u63a5\u53e3<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u5b9e\u9645\u5e94\u7528\u793a\u4f8b<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">1. \u8ba1\u7b97\u56fe\u7684\u8fde\u901a\u5206\u91cf<\/h3>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nfunc countComponents(n int, edges &#x5B;]&#x5B;]int) int {\n    uf := NewUnionFind(n)\n    for _, edge := range edges {\n        uf.Union(edge&#x5B;0], edge&#x5B;1])\n    }\n    return uf.count\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">2. \u5224\u65ad\u56fe\u4e2d\u662f\u5426\u6709\u73af<\/h3>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; gutter: true; title: ; notranslate\" title=\"\">\nfunc hasCycle(n int, edges &#x5B;]&#x5B;]int) bool {\n    uf := NewUnionFind(n)\n    for _, edge := range edges {\n        x, y := edge&#x5B;0], edge&#x5B;1]\n        if uf.Find(x) == uf.Find(y) {\n            return true\n        }\n        uf.Union(x, y)\n    }\n    return false\n}\n<\/pre><\/div>\n\n\n<h3 class=\"wp-block-heading\">3. \u670b\u53cb\u5708\u95ee\u9898<\/h3>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: go; title: ; notranslate\" title=\"\">\nfunc findCircleNum(isConnected &#x5B;]&#x5B;]int) int {\n    n := len(isConnected)\n    uf := NewUnionFind(n)\n    for i := 0; i &lt; n; i++ {\n        for j := i + 1; j &lt; n; j++ {\n            if isConnected&#x5B;i]&#x5B;j] == 1 {\n                uf.Union(i, j)\n            }\n        }\n    }\n    return uf.count\n}\n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">\u6027\u80fd\u5206\u6790<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a<br>\u2022 \u4ec5\u8def\u5f84\u538b\u7f29\u6216\u6309\u79e9\u5408\u5e76\uff1aO(alpha(n))<br>\u2022 \u540c\u65f6\u4f7f\u7528\u8def\u5f84\u538b\u7f29\u548c\u6309\u79e9\u5408\u5e76\uff1aO(alpha(n))<\/li>\n<\/ul>\n\n\n\n<p>\u5176\u4e2dalpha(n)\u662f\u53cd\u963f\u514b\u66fc\u51fd\u6570\uff0c\u589e\u957f\u6781\u5176\u7f13\u6162\uff0c\u53ef\u4ee5\u8ba4\u4e3a\u662f\u5e38\u6570\u65f6\u95f4\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n)<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u603b\u7ed3<\/h2>\n\n\n\n<p>\u5e76\u67e5\u96c6\u662f\u4e00\u79cd\u9ad8\u6548\u5904\u7406\u52a8\u6001\u8fde\u901a\u6027\u95ee\u9898\u7684\u6570\u636e\u7ed3\u6784\u3002\u901a\u8fc7\u8def\u5f84\u538b\u7f29\u548c\u6309\u79e9\u5408\u5e76\u4f18\u5316\uff0c\u53ef\u4ee5\u8fbe\u5230\u63a5\u8fd1\u5e38\u6570\u65f6\u95f4\u7684\u64cd\u4f5c\u590d\u6742\u5ea6\u3002Golang\u7684\u7b80\u6d01\u8bed\u6cd5\u4f7f\u5176\u5b9e\u73b0\u5e76\u67e5\u96c6\u5c24\u4e3a\u4f18\u96c5\uff0c\u9002\u5408\u5728\u5404\u79cd\u9700\u8981\u5904\u7406\u8fde\u901a\u6027\u95ee\u9898\u7684\u573a\u666f\u4e2d\u4f7f\u7528\u3002<\/p>\n\n\n\n<p>\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u6839\u636e\u5177\u4f53\u9700\u6c42\u9009\u62e9\u5408\u9002\u7684\u4f18\u5316\u7b56\u7565\u548c\u5f00\u6e90\u5b9e\u73b0\u53ef\u4ee5\u5927\u5927\u63d0\u9ad8\u5f00\u53d1\u6548\u7387\u548c\u8fd0\u884c\u6027\u80fd\u3002\u5bf9\u4e8e\u5927\u591a\u6570\u573a\u666f\uff0c\u540c\u65f6\u4f7f\u7528\u8def\u5f84\u538b\u7f29\u548c\u6309\u79e9\u5408\u5e76\u7684\u5b9e\u73b0\u662f\u6700\u4f73\u9009\u62e9\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ec0\u4e48\u662f\u5e76\u67e5\u96c6\uff1f \u5e76\u67e5\u96c6(Union-Find)\u662f\u4e00\u79cd\u6811\u578b\u7684\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5904\u7406\u4e00\u4e9b\u4e0d\u76f8\u4ea4\u96c6\u5408\u7684\u5408\u5e76(Union) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":487,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[],"class_list":["post-486","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/486","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=486"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/486\/revisions"}],"predecessor-version":[{"id":804,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/486\/revisions\/804"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/media\/487"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=486"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=486"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}