{"id":111,"date":"2026-03-13T14:47:32","date_gmt":"2026-03-13T06:47:32","guid":{"rendered":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/?p=111"},"modified":"2026-03-13T14:47:32","modified_gmt":"2026-03-13T06:47:32","slug":"tarjan%e7%ae%97%e6%b3%95%e6%9c%89%e5%90%91%e5%9b%be%ef%bc%8c%e6%97%a0%e5%90%91%e5%9b%be","status":"publish","type":"post","link":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/2026\/03\/13\/tarjan%e7%ae%97%e6%b3%95%e6%9c%89%e5%90%91%e5%9b%be%ef%bc%8c%e6%97%a0%e5%90%91%e5%9b%be\/","title":{"rendered":"tarjan\u7b97\u6cd5(\u6709\u5411\u56fe\uff0c\u65e0\u5411\u56fe)"},"content":{"rendered":"\n<p>P2863\u5976\u725b\u821e\u4f1a(\u6709\u5411\u56fe): <a href=\"https:\/\/www.luogu.com.cn\/problem\/P2863\">https:\/\/www.luogu.com.cn\/problem\/P2863<\/a><\/p>\n\n\n\n<p><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream>\n#include &lt;vector>\n#include &lt;stack>\n\nusing namespace std;\nvector&lt;int> a&#91;300000];\nint low&#91;300000], dfn&#91;300000], cnt, nu, isHave&#91;300000], tt;\nbool ins&#91;300000];\nstack&lt;int> s;\n\nvoid sout(int ss) {\n\tisHave&#91;tt]++;\n\tins&#91;ss] = 0;\n\ts.pop();\n}\n\nvoid dfs(int x, int fa) {\n\ts.push(x);\n\tins&#91;x] = 1;\n    dfn&#91;x] = ++nu;\n    low&#91;x] = nu;\n    for (int to : a&#91;x]) {\n        if (!dfn&#91;to]) {\n\t        dfs(to, x);\n\t        low&#91;x] = min(low&#91;x], low&#91;to]);\n        } else if(ins&#91;to]) low&#91;x] = min(low&#91;x], dfn&#91;to]);\n    }\n\t\n    if (dfn&#91;x] == low&#91;x]) {\n    \ttt++;\n    \twhile (s.top() != x) {\n    \t\tsout(s.top());\n\t\t}\n\t\tsout(x);\n\t\t\n\t}\n\t\n}\n\n\nint main() {\n     int m, n;\n     cin >> n >> m;\n     for (int i=1;i&lt;=m;i++) {\n         int x, y;\n         cin >> x >> y;\n         a&#91;x].push_back(y);\n     }\n    for (int i=1;i&lt;=n;i++) {\n    \tif (!dfn&#91;i]) dfs(i, i);\n    }\n    for (int i=1;i&lt;=n;i++) {\n    \tif (isHave&#91;i] > 1) cnt++;\n\t}\n    cout &lt;&lt; cnt &lt;&lt; endl;\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p>\u672a\u5b8c\u5f85\u7eed<\/p>\n","protected":false},"excerpt":{"rendered":"<p>P2863\u5976\u725b\u821e\u4f1a(\u6709\u5411\u56fe):&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-111","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/111","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=111"}],"version-history":[{"count":1,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/111\/revisions"}],"predecessor-version":[{"id":112,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/posts\/111\/revisions\/112"}],"wp:attachment":[{"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/\u9f50\u6cb3\u4e00\u4e2d.cn\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}