{"id":285,"date":"2019-10-18T21:08:08","date_gmt":"2019-10-18T13:08:08","guid":{"rendered":"https:\/\/blog.chtholly.moe\/?p=285"},"modified":"2021-08-21T18:13:28","modified_gmt":"2021-08-21T10:13:28","slug":"kosaraju","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=285","title":{"rendered":"Kosaraju"},"content":{"rendered":"<h1>Kosaraju \u901a\u8fc7\u4e00\u6b21\u6b63\u5411dfs\u548c\u4e00\u6b21\u53cd\u5411dfs\u6c42\u5f97\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(M+N)<\/h1>\n<p><!--more--><\/p>\n<h2>\u5176\u4e2dd[i]\u6570\u7ec4\u4fdd\u5b58dfs1\u65f6\u7b2ci\u4e2a\u8bbf\u95ee\u7684\u8282\u70b9\uff0cvis[i]\u4fdd\u5b58\u7b2ci\u4e2a\u8282\u70b9\u4f4d\u4e8e\u7b2ck\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u5185\uff0ck&lt;=n(\u5168\u90e8\u4e0d\u8fde\u901a).<\/h2>\n<pre>vector&lt;int&gt;sav[100002];\r\nvector&lt;int&gt;sav_[100002];\/\/\u53cd\u5411\u56fe\r\nint vis[100002],d[100002];\r\nint u[50002],v[50002],t;\/\/\u5b58\u8fb9\r\nint n,m;\r\nint cnt[100002];\/\/\u5b58\u50a8\u51fa\/\u5165\u5ea6<\/pre>\n<pre>void dfs1(int x){\r\n    vis[x]=1;\r\n    for(x\u7684\u51fa\u8fb9)\r\n        if(!vis[v])\r\n            dfs1(v)\/\/\u4e0d\u8981\u5199\u6210dfs()\r\n    d[++t]=x;\/\/\u7b2ct\u4e2a\u8bbf\u95eex\r\n}<\/pre>\n<pre>void dfs2(int x){\r\n    vis[x]=t;\r\n    for(\u53cd\u5411\u56fe\u4e2dx\u7684\u51fa\u8fb9)\r\n        if(!vis[v])\r\n            dfs2(v);\/\/\u4e0d\u8981\u5199\u6210dfs()\r\n}<\/pre>\n<pre>void Ko() {\r\n\tfor(int i=1; i&lt;=n; i++)\r\n            if(!vis[i])dfs1(i);\r\n\tt=0;\r\n\tmemset(vis,0,sizeof(vis));\r\n\tfor(int i=n; i&gt;=1; i--) {\/\/\u53cd\u5411\u904d\u5386d[i]\u4e2d\u7684\u5143\u7d20\r\n\t\tif(!vis[d[i]]) {\r\n\t\t\tt++;\r\n\t\t\tdfs2(d[i]);\r\n\t\t}\r\n\t}\r\n}<\/pre>\n<pre>void add(){\r\n\tx=read(),y=read();\r\n\tu[i]=x,v[i]=y;\r\n\tsav[x].push_back(y);\r\n\tsav_[y].push_back(x);\r\n}<\/pre>\n<h3>\u63a5\u4e0b\u6765\u662f\u5982\u4f55\u7edf\u8ba1\u51fa(\u5165)\u5ea6<\/h3>\n<p>\u9996\u5148\u679a\u4e3e\u6bcf\u4e00\u6761\u8fb9 i ,\u5982\u679c\u5176\u8d77\u70b9\u7ec8\u70b9\u4e0d\u5728\u540c\u4e00\u5f3a\u8fde\u901a\u5206\u91cf\u4e2d,\u5219<\/p>\n<p>cnt[vis[u[i]]]++(\u5f3a\u8fde\u901a\u5206\u91cf\u51fa\u5ea6) \u00a0 cnt[vis[v[i]]]++(\u5f3a\u8fde\u901a\u5206\u91cf\u5165\u5ea6)<\/p>\n<pre>for(int i=1; i&lt;=m; i++) {\r\n\tif(vis[u[i]]!=vis[v[i]])cnt[vis[u[i]]]++;\/\/v[i]\r\n        \/\/\u7edf\u8ba1\u4ee5u[i]\u6216v[i]\u4e3a\u6210\u5458\u7684\u5f3a\u8fde\u901a\u5206\u91cf\u51fa\u5ea6\/\u5165\u5ea6\r\n}<\/pre>\n<h2>\u5bf9\u4e8e\u51fa\u5ea6\u4e3a0\u7684\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u5176\u4e0d\u80fd\u5230\u8fbe\u4efb\u610f\u5176\u4ed6\u5f3a\u8fde\u901a\u5206\u91cf \u00a0 \u00a0 \u00a0 \u5bf9\u4e8e\u5165\u5ea6\u4e3a0\u7684\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u4efb\u610f\u5176\u4ed6\u5f3a\u8fde\u901a\u5206\u91cf\u5747\u4e0d\u80fd\u5230\u8fbe<\/h2>\n","protected":false},"excerpt":{"rendered":"<p>Kosaraju \u901a\u8fc7\u4e00\u6b21\u6b63\u5411dfs\u548c\u4e00\u6b21\u53cd\u5411dfs\u6c42\u5f97\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(M+N)<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-285","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=285"}],"version-history":[{"count":2,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/285\/revisions"}],"predecessor-version":[{"id":338,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/285\/revisions\/338"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}