{"id":246,"date":"2025-08-11T16:18:24","date_gmt":"2025-08-11T08:18:24","guid":{"rendered":"http:\/\/www.tgwttt.xyz\/?p=246"},"modified":"2025-11-24T16:38:57","modified_gmt":"2025-11-24T08:38:57","slug":"%e5%b9%b6%e6%9f%a5%e9%9b%86","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=246","title":{"rendered":"\u5e76\u67e5\u96c6"},"content":{"rendered":"\n

\u4ee3\u7801\u4ed3\u5e93\uff1ahttps:\/\/gitee.com\/tgwTTT\/data-structure\/tree\/master\/Gragh<\/a><\/p>\n\n\n\n

\u5e76\u67e5\u96c6\u539f\u7406<\/strong><\/p>\n\n\n\n

\u5728\u4e00\u4e9b\u5e94\u7528\u95ee\u9898\u4e2d\uff0c\u9700\u8981\u5c06n\u4e2a\u4e0d\u540c\u7684\u5143\u7d20\u5212\u5206\u6210\u4e00\u4e9b\u4e0d\u76f8\u4ea4\u7684\u96c6\u5408\u3002\u5f00\u59cb\u65f6\uff0c\u6bcf\u4e2a\u5143\u7d20\u81ea\u6210\u4e00\u4e2a\u5355\u5143\u7d20\u96c6\u5408\uff0c\u7136\u540e\u6309\u4e00\u5b9a\u7684\u89c4\u5f8b\u5c06\u5f52\u4e8e\u540c\u4e00\u7ec4\u5143\u7d20\u7684\u96c6\u5408\u5408\u5e76\u3002\u5728\u6b64\u8fc7\u7a0b\u4e2d\u8981\u53cd\u590d\u7528\u5230\u67e5\u8be2\u67d0\u4e00\u4e2a\u5143\u7d20\u5f52\u5c5e\u4e8e\u90a3\u4e2a\u96c6\u5408\u7684\u8fd0\u7b97\u3002\u9002\u5408\u4e8e\u63cf\u8ff0\u8fd9\u7c7b\u95ee\u9898\u7684\u62bd\u8c61\u6570\u636e\u7c7b\u578b\u79f0\u4e3a\u5e76\u67e5\u96c6(union-find set)\u3002
<\/p>\n\n\n\n

\u6bd4\u5982\u5f53\u572810\u4e2a\u4eba\u5185\uff0c\u6211\u8ba4\u8bc6\u4f60\uff0c\u4f60\u8ba4\u8bc6\u4ed6\uff0c\u6211\u4eec\u4e09\u4e2a\u5c31\u53eb\u505a\u4e00\u4e2a\u5c0f\u56e2\u4f53\uff0c\u82e5\u8981\u6c42\u6709\u51e0\u4e2a\u5c0f\u56e2\u4f53\u5462\uff1f<\/p>\n\n\n\n

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

\u6b64\u65f6\u6211\u4eec\u5e76\u67e5\u96c6\u5c31\u53d1\u6325\u4f5c\u7528\u4e86\u3002<\/p>\n\n\n\n

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

\u6570\u7ec4\u4e0b\u6807\u8868\u793a\u7236\u8282\u70b9\u4e0b\u6807\uff0c\u82e5\u4e3a\u8d1f\u5219\u8868\u793a\u5176\u4e3a\u7236\u8282\u70b9<\/p>\n\n\n\n

\u5148\u5c06\u5168\u4f53\u6570\u636e\u7f6e\u4e3a-1,\u5982\u82e5\u4e24\u8005\u95f4\u6709\u5173\u7cfb\uff0c\u5219\u627e\u5230\u4e24\u4eba\u7684\u7236\u8282\u70b9\u9009\u62e9\u5176\u4e2d\u4e00\u4e2a\u4f5c\u4e3a\u53e6\u4e00\u4e2a\u7236\u8282\u70b9\uff0c\u5c06\u5176\u503c\u7f6e\u4e3a\u5176\u7236\u8282\u70b9\u7684\u4e0b\u6807\u3002<\/p>\n\n\n\n

\u6700\u540e\u5bfb\u627e\u5176\u4e2d\u6709\u51e0\u4e2a\u8d1f\u6570\uff0c\u5224\u65ad\u5176\u6709\u51e0\u4e2a\u5c0f\u56e2\u4f53<\/p>\n\n\n\n

\u4e0b\u9762\u662f\u4ee3\u7801\u5b9e\u73b0<\/p>\n\n\n\n

class UnionFindSet\n{\npublic:\n\tUnionFindSet(size_t n):_ufs(n,-1) {}\n\tvoid Union(int x1, int x2) {\/\/\u5408\u5e76\n\t\tint root1 = FindRoot(x1);\n\t\tint root2 = FindRoot(x2);\n\t\tif (root1 == root2) {\n\t\t\treturn;\n\t\t}\n\t\telse {\n\t\t\t_ufs[root1] += _ufs[root2];\n\t\t\t_ufs[root2] = root1;\n\t\t}\n\t}\n\tint FindRoot(int x) {\n\t\tint parent = x;\n\t\twhile (_ufs[parent]>=0) {\n\t\t\tparent = _ufs[parent];\n\t\t}\n\t\treturn parent;\n\t}\/\/\u627e\u6839\n\tbool Inset(int x1,int x2){\n\t\treturn FindRoot(x1) == FindRoot(x2);\n\t}\/\/\u662f\u5426\u5728\u540c\u4e00\u4e2a\u96c6\u5408\n\tsize_t SetSize(){\n\t\tint count = 0;\n\t\tfor (auto i : _ufs) {\n\t\t\tif (i < 0)count++;\n\t\t}\n\t\treturn count;\n\t}\/\/\u6709\u51e0\u4e2a\u96c6\u5408\n\nprivate:\n\tvector_ufs;\n};\n<\/code><\/pre>\n\n\n\n
\u4f46\u662f\u51fa\u73b0\u4e86\u4e00\u4e2a\u65b0\u95ee\u9898\uff0c\u5373\u6bcf\u5f53\u6811\u7684\u6df1\u5ea6\u975e\u5e38\u5927\u65f6\uff0c\u5c31\u4f1a\u5f71\u54cd\u5230\u6211\u4eec\u7684\u6548\u7387<\/p>\n\n\n\n
\u4e0b\u9762\u662f\u89e3\u51b3\u65b9\u6cd5\uff1a<\/p>\n\n\n\n
\u6bcf\u6b21\u5bfb\u627e\u6839\u8282\u70b9\u65f6\uff0c\u6bcf\u5f53\u6df1\u5ea6\u8d85\u8fc72\u65f6\uff0c\u90fd\u5c06\u5176\u6302\u5728\u6839\u8282\u70b9\u4e0b\uff1a
<\/p>\n\n\n\n
int FindRoot(int x) {\n\tint parent = x;\n\twhile (_ufs[parent]>=0) {\n\t\tparent = _ufs[parent];\n\t}\n\t_ufs[x] = parent;\/\/\u8def\u5f84\u538b\u7f29\n\treturn parent;\n}\/\/\u627e\u6839<\/code><\/pre>\n\n\n\n
\u4e0b\u9762\u662f\u9898\u76ee\u7ec3\u4e60\uff1a<\/p>\n\n\n\n
LCR 116. \u7701\u4efd\u6570\u91cf – \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n
\u7b54\u6848\uff1a<\/p>\n\n\n\n
class Solution {\npublic:\n    int findCircleNum(vector>& isConnected) {\n        \/\/ \u624b\u52a8\u63a7\u5236\u5e76\u67e5\u96c6\n        vector ufs(isConnected.size(), -1);\n        \/\/ \u67e5\u627e\u6839\n        auto findRoot = [&ufs](int x) {\n            while (ufs[x] >= 0)\n                x = ufs[x];\n            return x;\n        };\n        for (size_t i = 0; i < isConnected.size(); ++i) {\n            for (size_t j = 0; j < isConnected[i].size(); ++j) {\n                if (isConnected[i][j] == 1) {\n                    \/\/ \u5408\u5e76\u96c6\u5408\n                    int root1 = findRoot(i);\n                    int root2 = findRoot(j);\n                    if (root1 != root2) {\n                        ufs[root1] += ufs[root2];\n                        ufs[root2] = root1;\n                    }\n                }\n            }\n        }\n        int n = 0;\n        for (auto e : ufs) {\n            if (e < 0)\n                ++n;\n        }\n        return n;\n    }\n};\n    <\/code><\/pre>\n\n\n\n
\u4eca\u5929\u7684\u8ddf\u65b0\u5c31\u5230\u8fd9\uff0c\u5982\u6709\u4e0d\u5bf9\u6b22\u8fce\u8bc4\u8bba\u533a\u6307\u51fa\uff01\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4ee3\u7801\u4ed3\u5e93\uff1ahttps:\/\/gitee.com\/tgwTTT\/data-structure\/tree\/maste…<\/p>\n","protected":false},"author":1,"featured_media":249,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[4,6],"tags":[],"class_list":["post-246","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","category-6"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=246"}],"version-history":[{"count":5,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/246\/revisions"}],"predecessor-version":[{"id":853,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/246\/revisions\/853"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/249"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}