{"id":410,"date":"2022-10-06T20:56:18","date_gmt":"2022-10-06T12:56:18","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=410"},"modified":"2024-09-12T09:31:00","modified_gmt":"2024-09-12T01:31:00","slug":"%e5%9b%be%e7%9a%84%e5%89%b2%e7%82%b9-%e5%8f%88%e8%b0%88tarjan","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=410","title":{"rendered":"\u56fe\u7684\u5272\u70b9\u2014\u53c8\u8c08Tarjan"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/s2.ax1x.com\/2019\/07\/08\/ZDwEVg.md.jpg\" alt=\"\" \/><\/p>\n<p>\u4ee5\u4e0b\u662f\u5272\u70b9\u7684\u5b9a\u4e49\uff1a<\/p>\n<blockquote>\n<h2>\u5728\u4e00\u4e2a\u65e0\u5411\u56fe\u4e2d\uff0c\u5982\u679c\u6709\u4e00\u4e2a\u9876\u70b9\u96c6\u5408\uff0c\u5220\u9664\u8fd9\u4e2a\u9876\u70b9\u96c6\u5408\u4ee5\u53ca\u8fd9\u4e2a\u96c6\u5408\u4e2d\u6240\u6709\u9876\u70b9\u76f8\u5173\u8054\u7684\u8fb9\u4ee5\u540e\uff0c\u56fe\u7684\u8fde\u901a\u5206\u91cf\u589e\u591a\uff0c\u5c31\u79f0\u8fd9\u4e2a\u70b9\u96c6\u4e3a\u5272\u70b9\u96c6\u5408\u3002<\/h2>\n<h2>\u5982\u679c\u67d0\u4e2a\u5272\u70b9\u96c6\u5408\u53ea\u542b\u6709\u4e00\u4e2a\u9876\u70b9X\uff08\u4e5f\u5373{X}\u662f\u4e00\u4e2a\u5272\u70b9\u96c6\u5408\uff09\uff0c\u90a3\u4e48X\u79f0\u4e3a\u4e00\u4e2a\u5272\u70b9\u3002\u2014\u2014\u6765\u81ea\u767e\u5ea6\u767e\u79d1<\/h2>\n<hr \/>\n<\/blockquote>\n<p>\u7528Tarjan\u7b97\u6cd5\u6c42\u5272\u70b9\u7684\u57fa\u672c\u601d\u60f3\u662f\uff1a<\/p>\n<ul>\n<li>\u5982\u679c\u8fd9\u4e2a\u70b9\u662f\u6839\u8282\u70b9\uff0c\u4e14\u6709\u4e24\u4e2a\u53ca\u4ee5\u4e0a\u7684\u5b50\u6811\uff0c\u90a3\u4e48\u4ed6\u662f\u5272\u70b9\uff0c\u56e0\u4e3a\u53bb\u6389\u4ed6\u4e4b\u540e\u4ed6\u7684\u5b50\u6811\u76f8\u4e92\u4e0d\u80fd\u5230\u8fbe<\/li>\n<li>\n<p>\u5982\u679c\u8fd9\u4e2a\u70b9\u662f\u975e\u6839\u8282\u70b9\uff0c\u5219\u7528LOW\u503c\u4e0eDFN\u503c\u53bb\u7ef4\u62a4\u4ed6\u7684\u72b6\u6001\uff0c\u4e14\u5982\u679c\u5bf9\u4e8e\u8fb9x-&gt;y\uff0c\u5982\u679clow[ y ]&gt;=dfn[ x ]\uff0c\u5219\u8bf4\u660ey\u662f\u5272\u70b9<\/p>\n<p>\u6240\u4ee5\u4e0e\u7528Tarjan\u6c42\u5f3a\u8fde\u901a\u5206\u91cf\u65f6\u4e0d\u540c\u7684\u662f\uff0c\u4e3a\u4e86\u5224\u65ad\u4e00\u4e2a\u70b9\u662f\u5426\u662f\u6839\uff0c\u6211\u4eec\u9700\u8981\u4f20\u9012\u4e24\u4e2a\u53c2\u6570\u5230\u51fd\u6570\u4e2d<\/p>\n<p>\u4e3b\u7a0b\u5e8f\u4e2d\uff1a<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"language-cpp\">for(int i=1;i&lt;=n;i++)\n        if(!dfn[i])\n            tarjan(i,i);<\/code><\/pre>\n<p>\u5b50\u7a0b\u5e8f\uff1a<\/p>\n<pre><code class=\"language-cpp\">int dfn[maxn],low[maxn],tmmk=0;\nbool cut[maxn];\nvoid tarjan(int x,int rt){\n    dfn[x]=low[x]=++tmmk;\n    int son=0;\n    for(int i=head[x];i;i=nxt[i]){\n        int y=G[i].y;\n        if(!dfn[y]){\n            tarjan(y,rt);\n            low[x]=min(low[x],low[y]);\n            if(low[y]&gt;=dfn[x] &amp;&amp; x!=rt)\n                cut[x]=true;\n            if(x==rt)son++;\n        }\n        low[x]=min(low[x],dfn[y]);\n    }\n    if(x==rt &amp;&amp; son&gt;1)\n        cut[x]=true;\n}<\/code><\/pre>\n<p>\u81f3\u6b64\uff0c\u6240\u6709cut\u503c\u4e3atrue\u7684\u70b9\u90fd\u662f\u5272\u70b9\u4e86<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ee5\u4e0b\u662f\u5272\u70b9\u7684\u5b9a\u4e49\uff1a \u5728\u4e00\u4e2a\u65e0\u5411\u56fe\u4e2d\uff0c\u5982\u679c\u6709\u4e00\u4e2a\u9876\u70b9\u96c6\u5408\uff0c\u5220\u9664\u8fd9\u4e2a\u9876\u70b9\u96c6\u5408\u4ee5\u53ca\u8fd9\u4e2a [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-410","post","type-post","status-publish","format-standard","hentry","category-2"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=410"}],"version-history":[{"count":1,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/410\/revisions"}],"predecessor-version":[{"id":736,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/410\/revisions\/736"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}