{"id":797,"date":"2023-11-03T13:19:29","date_gmt":"2023-11-03T05:19:29","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=797"},"modified":"2023-11-03T13:19:29","modified_gmt":"2023-11-03T05:19:29","slug":"%e6%b5%85%e8%b0%88%e5%8f%8c%e8%bf%9e%e9%80%9a%e5%88%86%e9%87%8f","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2023\/11\/03\/%e6%b5%85%e8%b0%88%e5%8f%8c%e8%bf%9e%e9%80%9a%e5%88%86%e9%87%8f\/","title":{"rendered":"\u6d45\u8c08\u53cc\u8fde\u901a\u5206\u91cf"},"content":{"rendered":"<h1>\u524d\u7f6e\u77e5\u8bc6<\/h1>\n<ul>\n<li><a href=\"https:\/\/oi-wiki.org\/graph\/concept\/\">\u56fe\u8bba\u76f8\u5173\u6982\u5ff5<\/a><\/li>\n<li><a href=\"https:\/\/oi-wiki.org\/graph\/cut\/\">\u5272\u70b9\u548c\u6865<\/a><\/li>\n<li><a href=\"https:\/\/oi-wiki.org\/graph\/scc\/\">\u5f3a\u8fde\u901a\u5206\u91cf<\/a><\/li>\n<\/ul>\n<h1>\u70b9\u53cc\u8fde\u901a\u5206\u91cf<\/h1>\n<p>\u5728\u4e00\u4e2a\u65e0\u5411\u56fe\u4e2d\uff0c\u82e5\u5220\u9664\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u8fd9\u4e2a\u56fe\u8fd8\u80fd\u8fde\u901a\uff0c\u5219\u79f0\u8fd9\u4e2a\u56fe\u4e3a<strong>\u70b9\u53cc\u8fde\u901a<\/strong><\/p>\n<p>\u4f8b\u9898\uff1a<a href=\"https:\/\/www.luogu.com.cn\/problem\/P8435\">P8435 \u3010\u6a21\u677f\u3011\u70b9\u53cc\u8fde\u901a\u5206\u91cf<\/a><\/p>\n<p>\u5728\u4e66\u5199\u4ee3\u7801\u7684\u65f6\u5019\u6709\u9700\u8981\u6ce8\u610f\u7684\u5730\u65b9\u4f1a\u5728\u7a0b\u5e8f\u4e2d\u6807\u6ce8\u3002<\/p>\n<pre><code class=\"language-cpp\">#include &lt;bits\/stdc++.h&gt; \nusing namespace std;\nconst int maxn = 5e5 + 5;\n\nint n, m;\nvector&lt;int&gt; G[maxn], ans[maxn];\nint dfn[maxn], low[maxn], cnt;\nint top, stk[2000005];\n\nvoid dfs(int x, int fa) {\n    dfn[x] = low[x] = ++dfn[0];\n    stk[++top] = x;\n    int son = 0;\n    for(auto to : G[x]) {\n        if(!dfn[to]) {\n            if(to == fa) continue;\n            son++;\n            dfs(to, x);\n            low[x] = min(low[x], low[to]);                                  \/\/\u6ce8\u610fdfn\u548clow\u6570\u7ec4\u6709\u6ca1\u6709\u641e\u6df7 \n            if(low[to] &gt;= dfn[x]) {                      \n                cnt++;\n                int tmp = 0;\n                while(stk[top + 1] != to) ans[cnt].push_back(stk[top--]);\n                ans[cnt].push_back(x);\n            }\n\n        }\n        else if(to != fa)low[x] = min(low[x],dfn[to]);\n    }\n    if(son == 0 &amp;&amp; fa == 0) ans[++cnt].push_back(x);                        \/\/\u4e0d\u8981\u5fd8\u8bb0\u5224\u8bfb\u9876\u70b9 \n}\n\nint main() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n\/\/  freopen(&quot;AKIOI.in&quot;, &quot;r&quot;, stdin);\n\/\/  freopen(&quot;AKIOI.out&quot;, &quot;w&quot;, stdout);\n    cin &gt;&gt; n &gt;&gt; m;\n    for(int i = 1, u, v; i &lt;= m; i++) {\n        cin &gt;&gt; u &gt;&gt; v;\n        G[u].push_back(v);\n        G[v].push_back(u);\n    }\n    for(int i = 1; i &lt;= n; i++) {\n        if(dfn[i] != 0) continue;\n        top = 0;                    \/\/\u4e0d\u8981\u5fd8\u8bb0\u6e05\u7a7a\u6808 \n        dfs(i, 0);\n    }\n    cout &lt;&lt; cnt &lt;&lt; &#039;\\n&#039;;\n    for(int i = 1; i &lt;= cnt; i++) {\n        cout &lt;&lt; ans[i].size() &lt;&lt; &quot; &quot;;\n        for(auto j : ans[i]) cout &lt;&lt; j &lt;&lt; &quot; &quot;;\n        cout &lt;&lt; &quot;\\n&quot;;\n    }\n    return 0;\n\n}<\/code><\/pre>\n<h1>\u8fb9\u53cc\u8fde\u901a\u5206\u91cf<\/h1>\n<p>\u5728\u4e00\u4e2a\u65e0\u5411\u56fe\u4e2d\uff0c\u82e5\u5220\u9664\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u6761\u8fb9\uff0c\u8fd9\u4e2a\u56fe\u8fd8\u80fd\u8fde\u901a\uff0c\u5219\u79f0\u8fd9\u4e2a\u56fe\u4e3a<strong>\u70b9\u53cc\u8fde\u901a<\/strong><\/p>\n<p>\u4f8b\u9898\uff1a<a href=\"https:\/\/www.luogu.com.cn\/problem\/P8436\">P8436 \u3010\u6a21\u677f\u3011\u8fb9\u53cc\u8fde\u901a\u5206\u91cf<\/a><\/p>\n<p>\u5728\u4e66\u5199\u4ee3\u7801\u7684\u65f6\u5019\u6709\u9700\u8981\u6ce8\u610f\u7684\u5730\u65b9\u4f1a\u5728\u7a0b\u5e8f\u4e2d\u6807\u6ce8\u3002<\/p>\n<pre><code class=\"language-cpp\">#include &lt;iostream&gt;\n#include &lt;stack&gt;\n#include &lt;vector&gt;\nusing namespace std;\nconst int maxn = 5e5 + 5;\n\nint n, m, cnt = 0;\nvector&lt;pair&lt;int, int&gt; &gt; G[maxn];\nvector&lt;int&gt; ans[maxn];\nint dfn[maxn], low[maxn];\nstack&lt;int&gt; stk;\n\nvoid tarjan(int x, int fa) {\n    low[x] = dfn[x] = ++dfn[0];\n        stk.push(x);\n    for(auto i : G[x]) {\n        int to = i.first, it = i.second;    \n        if (it == (fa ^ 1)) continue;           \/\/\u5229\u7528\u4f4d\u8fd0\u7b97\u5224\u65ad\u91cd\u8fb9 \n        if(!dfn[to]) {\n            tarjan(to, it);\n            low[x] = min(low[x], low[to]);      \/\/dfn\u548clow\u4e0d\u8981\u641e\u9519 \n        }\n        else low[x] = min(low[x], dfn[to]);\n    }\n    if(dfn[x] == low[x]) {\n        cnt++;\n        ans[cnt].push_back(x);\n        while(!stk.empty() &amp;&amp; stk.top() != x) {ans[cnt].push_back(stk.top()), stk.pop();}   \/\/\u51fa\u6808\u7684\u64cd\u4f5c\u9700\u8981\u6ce8\u610f \n        stk.pop();\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    \/\/ freopen(&quot;AKIOI.in&quot;, &quot;r&quot;, stdin);\n    \/\/ freopen(&quot;AKIOI.out&quot;, &quot;w&quot;, stdout);\n    cin &gt;&gt; n &gt;&gt; m;\n    for(int i = 1, u, v; i &lt;= m; i++) {\n        cin &gt;&gt; u &gt;&gt; v;\n        G[u].push_back(make_pair(v, i * 2));        \/\/\u7ed9\u6bcf\u6761\u8fb9\u7f16\u53f7\u65b9\u4fbf\u53bb\u91cd \n        G[v].push_back(make_pair(u, i * 2 + 1));\n    }\n    for(int i = 1; i &lt;= n; i++) {\n        if(!dfn[i]) tarjan(i, 0);\n    }\n    cout &lt;&lt; cnt &lt;&lt; &quot;\\n&quot;;\n    for(int i = 1; i &lt;= cnt; i++) {\n        cout &lt;&lt; ans[i].size() &lt;&lt; &quot; &quot;;\n        for(auto j : ans[i]) cout &lt;&lt; j &lt;&lt; &quot; &quot;;\n        cout &lt;&lt; &quot;\\n&quot;;\n    }\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u524d\u7f6e\u77e5\u8bc6 \u56fe\u8bba\u76f8\u5173\u6982\u5ff5 \u5272\u70b9\u548c\u6865 \u5f3a\u8fde\u901a\u5206\u91cf \u70b9\u53cc\u8fde\u901a\u5206\u91cf \u5728\u4e00\u4e2a\u65e0\u5411\u56fe\u4e2d\uff0c\u82e5\u5220\u9664\u56fe\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\uff0c\u8fd9\u4e2a\u56fe\u8fd8\u80fd [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[27,28],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/797"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=797"}],"version-history":[{"count":1,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/797\/revisions"}],"predecessor-version":[{"id":798,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/797\/revisions\/798"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=797"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=797"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=797"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}