{"id":42,"date":"2025-04-01T01:37:14","date_gmt":"2025-03-31T17:37:14","guid":{"rendered":"http:\/\/120.76.99.214\/?p=42"},"modified":"2025-11-24T16:43:46","modified_gmt":"2025-11-24T08:43:46","slug":"tanji%e5%bc%ba%e8%81%94%e9%80%9a%e5%88%86%e9%87%8f%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=42","title":{"rendered":"tanji\u5f3a\u8054\u901a\u5206\u91cf\u7b97\u6cd5"},"content":{"rendered":"\n<p>\u535a\u4e3b\u6700\u8fd1\u5728\u5199\u9898\u65f6\u9047\u5230\u4e00\u4e2a\u56fe\u8bba\u7684\u9898\uff0c\u7531\u4e8e\u535a\u4e3b\u5bf9\u56fe\u8bba\u7814\u7a76\u4e0d\u6df1\u548c\u79bb\u6563\u6570\u5b66\u786e\u5b9e\u6ca1\u5b66\u597d\uff0c\u770b\u5230\u8fd9\u9053\u9898\u53ea\u80fd\u5927\u773c\u77aa\u5c0f\u773c\uff0c\u65e0\u4ece\u4e0b\u624b\uff0c\u540e\u6765\u770b\u4e86\u9898\u89e3\u8fd8\u662f\u65e0\u4ece\u4e0b\u624b\uff0c\u9898\u89e3\u4e2d\u7684\u8054\u901a\u5206\u91cf\u548c\u7b97\u6cd5\u4e00\u65e0\u6240\u77e5\u3002\u540e\u6765\u7ecf\u8fc7\u535a\u4e3b\u7684\u4e0d\u65ad\u5b66\u4e60\uff0c\u7ec8\u4e8e\u641e\u660e\u767d\u4e86\u8fd9\u9053\u9898\uff0c\u7279\u5730\u5206\u4eab\u4e00\u4e0b\u6211\u7684\u5b66\u4e60\u5fc3\u5f97\uff0c\u9898\u76ee\u5982\u4e0b<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"837\" height=\"677\" src=\"http:\/\/120.76.99.214\/wp-content\/uploads\/2025\/04\/image.png\" alt=\"\" class=\"wp-image-43\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/04\/image.png 837w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/04\/image-300x243.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/04\/image-768x621.png 768w\" sizes=\"auto, (max-width: 837px) 100vw, 837px\" \/><\/figure>\n\n\n\n<p>    <\/p>\n\n\n\n<p>\u8fd9\u9053\u9898\u6700\u6838\u5fc3\u7684\u70b9\u662f\u6c42\u51fa\u7b80\u5355\u56fe\u8054\u901a\u5206\u91cf\u7684\u6570\u91cf\u6700\u540e\u7684\u7ed3\u679cres=M-(N-1-(K-1))=M+K-N;<\/p>\n\n\n\n<p>M,N\u5df2\u7ecf\u77e5\u9053\u4e86\uff0c\u53ea\u9700\u8981\u6c42\u51fa\u8054\u901a\u5206\u91cf\u5373\u53ef\uff0c\u90a3\u4e48\u4ec0\u4e48\u4e8b\u8054\u901a\u5206\u91cf\u52d2\uff0c\u5b83\u53c8\u8be5\u5982\u4f55\u6c42\u51fa\u6765\u52d2\uff1f<\/p>\n\n\n\n<p><strong>\u8fde\u901a\u5206\u91cf<\/strong>\uff1a\u65e0\u5411\u56fe\u7684\u6781\u5927\u8fde\u901a\u5b50\u56fe\u79f0\u4e3a\u7684\u8fde\u901a\u5206\u91cf( Connected Component)\u3002<\/p>\n\n\n\n<p>\u6781\u5927\u8fde\u901a\u5b50\u56fe\u8bf4\u7684\u662f\uff0c\u5982\u679c\u5c06\u8fde\u901a\u5206\u91cf\u5916\u7684\u4efb\u610f\u4e00\u4e2a\u9876\u70b9\u6dfb\u52a0\u8fdb\u8fde\u901a\u5206\u91cf\u90fd\u4f1a\u9020\u6210\u4e0d\u8fde\u901a\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"700\" height=\"240\" src=\"http:\/\/120.76.99.214\/wp-content\/uploads\/2025\/04\/image-1.png\" alt=\"\" class=\"wp-image-44\" style=\"width:837px;height:auto\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/04\/image-1.png 700w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/04\/image-1-300x103.png 300w\" sizes=\"auto, (max-width: 700px) 100vw, 700px\" \/><\/figure>\n\n\n\n<p>\u5982\u4e0a\u56fea\u53ef\u4ee5\u5206\u6210\u56db\u4e2a\u8054\u901a\u5206\u91cf\u3002<\/p>\n\n\n\n<p>\u90a3\u4e48\u77e5\u9053\u4e86\u6982\u5ff5\u4e4b\u540e\u8be5\u5982\u4f55\u6c42\u89e3\uff1f<\/p>\n\n\n\n<p>\u6700\u5e38\u89c1\u7684\u65b9\u6cd5\u4e3adfs<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include <iostream>\n#include <vector>\nusing namespace std;\nvector<vector<int>> vt;\nvector<bool> vis;\nint N, M;\nvoid dfs(int num) {\n    vis[num] = true;\n    for (int neighbor : vt[num]) {\n        if (!vis[neighbor]) {\n            dfs(neighbor);\n        }\n    }\n}\nvoid solution() {\n    cin >> N >> M;\n    vt.resize(N + 1); \n    vis.resize(N + 1, false);\n    for (int i = 0; i < M; ++i) {\n        int u, v;\n        cin >> u >> v;\n        vt[u].push_back(v);\n        vt[v].push_back(u);\n    }\n\n    int K = 0;\n    for (int i = 1; i <= N; ++i) { \n        if (!vis[i]) {\n            K++;\n            dfs(i);\n        }\n    }\n  cout<<K;\n}\nint main() {\n    solution();\n    return 0;\n}\n\u53ea\u9700\u8981\u4e00\u4e2a\u8bb0\u5f55\u6570\u7ec4\uff0c\u8bb0\u5f55\u8282\u70b9\u6709\u6ca1\u6709\u88ab\u8bbf\u95ee\u5373\u53ef\uff0c\u5f53\u6328\u4e2a\u904d\u5386\u5b8c\u6240\u6709\u8282\u70b9\u7684K\u4e3a\u8054\u901a\u5206\u91cf\u6570\u91cf\n\u800c\u4e0a\u8ff0\u9898\u76ee\u53ea\u9700\u8981\u5728\u4e0a\u8ff0\u4ee3\u7801\u4e2d\u8f93\u51faM-(N-K)\u5c31\u53ef\u4ee5\u4e86\uff0c\u8fd9\u6837\u4e00\u770b\u662f\u4e0d\u662f\u5f88\u7b80\u5355\u5462\uff01\n   \u4eca\u5929\u7684\u8bb0\u5f55\u5c31\u5230\u8fd9\u4e86\uff0c\u656c\u8bf7\u671f\u5f85\u4e0b\u6b21\u66f4\u65b0\uff01\uff01\uff01<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u535a\u4e3b\u6700\u8fd1\u5728\u5199\u9898\u65f6\u9047\u5230\u4e00\u4e2a\u56fe\u8bba\u7684\u9898\uff0c\u7531\u4e8e\u535a\u4e3b\u5bf9\u56fe\u8bba\u7814\u7a76\u4e0d\u6df1\u548c\u79bb\u6563\u6570\u5b66\u786e\u5b9e\u6ca1\u5b66\u597d\uff0c\u770b\u5230\u8fd9\u9053\u9898\u53ea\u80fd\u5927\u773c\u77aa\u5c0f\u773c\uff0c\u65e0\u4ece\u4e0b&#8230;<\/p>\n","protected":false},"author":1,"featured_media":43,"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":[1],"tags":[],"class_list":["post-42","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/42","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=42"}],"version-history":[{"count":4,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/42\/revisions"}],"predecessor-version":[{"id":895,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/42\/revisions\/895"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/43"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=42"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=42"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}