{"id":404,"date":"2022-10-06T20:48:07","date_gmt":"2022-10-06T12:48:07","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=404"},"modified":"2024-09-12T09:31:50","modified_gmt":"2024-09-12T01:31:50","slug":"%e5%9b%be%e7%9a%84%e5%bc%ba%e8%bf%9e%e9%80%9a%e4%b8%8e%e7%bc%a9%e7%82%b9-tarjan%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=404","title":{"rendered":"\u56fe\u7684\u5f3a\u8fde\u901a\u4e0e\u7f29\u70b9\u2014Tarjan\u7b97\u6cd5"},"content":{"rendered":"

\"\"<\/p>\n

\u5148\u4ecb\u7ecd\u51e0\u4e2a\u57fa\u672c\u6982\u5ff5\uff1a<\/p>\n

    \n
  1. \u5f3a\u8fde\u901a\uff1a \u5728\u4e00\u4e2a\u6709\u5411\u56feG\u91cc\uff0c\u8bbe\u4e24\u4e2a\u70b9 a b\uff0c\u7531a\u6709\u4e00\u6761\u8def\u53ef\u4ee5\u8d70\u5230b\uff0c\u7531b\u53c8\u6709\u4e00\u6761\u8def\u53ef\u4ee5\u8d70\u5230a\uff0c\u6211\u4eec\u5c31\u53eb\u8fd9\u4e24\u4e2a\u9876\u70b9\uff08a\uff0cb\uff09\u5f3a\u8fde\u901a<\/li>\n
  2. \u5f3a\u8fde\u901a\u56fe\uff1a \u5982\u679c \u5728\u4e00\u4e2a\u6709\u5411\u56feG\u4e2d\uff0c\u6bcf\u4e24\u4e2a\u70b9\u90fd\u5f3a\u8fde\u901a\uff0c\u6211\u4eec\u5c31\u53eb\u8fd9\u4e2a\u56fe\uff0c\u5f3a\u8fde\u901a\u56fe<\/li>\n
  3. \u5f3a\u8fde\u901a\u5206\u91cf\uff1a\u5728\u4e00\u4e2a\u6709\u5411\u56feG\u4e2d\uff0c\u6709\u4e00\u4e2a\u5b50\u56fe\uff0c\u8fd9\u4e2a\u5b50\u56fe\u6bcf2\u4e2a\u70b9\u90fd\u6ee1\u8db3\u5f3a\u8fde\u901a\uff0c\u6211\u4eec\u5c31\u53eb\u8fd9\u4e2a\u5b50\u56fe\u53eb\u505a\u5f3a\u8fde\u901a\u5206\u91cf<\/li>\n<\/ol>\n
    \n

    \u5728Tarjan\u7b97\u6cd5\u4e2d\uff0c\u6bcf\u4e2a\u70b9\u88ab\u8d4b\u4e88\u4ee5\u4e0b\u4e24\u4e2a\u4fe1\u606f\uff1a<\/p>\n

    \u00b7DFN\u503c\uff0c\u5373\u8bbf\u95ee\u8fd9\u4e2a\u70b9\u7684\u65f6\u95f4\u6233\uff0c\u6bcf\u4e2a\u70b9\u7684DFN\u503c\u90fd\u662f\u552f\u4e00\u7684<\/p>\n

    \u00b7LOW\u503c\uff0c\u5373\u8fd9\u4e2a\u70b9\u80fd\u8bbf\u95ee\u5230\u7684\u6700\u65e9\u7684\u7956\u5148\u8282\u70b9\uff0c\u5982\u679c\u4ed6\u4e0d\u80fd\u5411\u4e0a\u8bbf\u95ee\uff0c\u90a3\u4e48LOW\u503c\u5c31\u662f\u4ed6\u81ea\u5df1<\/p>\n

    Tarjan\u7b97\u6cd5\u7684\u57fa\u672c\u6d41\u7a0b\u662f\uff1a\u4ece\u4e00\u4e2a\u70b9\u5f00\u59cb\u6df1\u641c\uff0c\u6bcf\u4e00\u4e2a\u70b9\u7684\u7684DFN\u503c\u548cLOW\u503c\u521d\u59cb\u5316\u4e3a\u65f6\u95f4\u6233\uff0c\u5c06\u5176\u538b\u6808\uff0c\u540c\u65f6\u7528\u5e03\u5c14\u6570\u7ec4v\u6765\u8bb0\u5f55\u8fd9\u4e2a\u70b9\u6709\u6ca1\u6709\u5728\u6808\u91cc\uff0c\u5047\u8bbe\u8fd9\u4e2a\u70b9\u662fx\uff0c\u538b\u6808\u540e\u5f00\u59cb\u67e5x\u7684\u90bb\u63a5\u70b9\uff0c\u5047\u8bbe\u90bb\u63a5\u70b9\u662fy\uff0c\u90a3\u4e48\u5982\u679cy\u6ca1\u6709\u88ab\u641c\u8fc7\uff08dfn[ y ]\u4e3a0\uff09\uff0c\u5c31\u9012\u5f52\u641c\u7d22y\uff0c\u7136\u540e\u5982\u679c\u641c\u5b8c\u4e86y\u7684low\u503c\u66f4\u5c0f\uff0c\u5219\u66f4\u65b0x\u7684low\u503c\uff0c\u5982\u679cy\u641c\u8fc7\u4e86\u4e14\u5728\u6808\u91cc\uff08v[ y ]\u4e3atrue\uff09\uff0c\u90a3\u4e48\u5982\u679cy\u7684dfn\u503c\u66f4\u5c0f\uff0c\u5219\u66f4\u65b0x\u7684low\u503c\u3002\u505a\u5230\u6b64\u65f6\uff0c\u6539\u5199\u9012\u5f52\u51fa\u53e3\u4e86\uff0c\u5982\u679cdfn[ x ]==low[ x ]\uff0c\u5219\u8bf4\u660e\u4ed6\u662f\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u5165\u53e3\uff0c\u6b64\u65f6\u6211\u4eec\u7684ans++\uff08\u627e\u5230\u4e86\u5f3a\u8fde\u901a\u5206\u91cf<\/em>1\uff09\uff0c\u5f39\u51fa\u6808\u91ccx\u53ca\u4ed6\u4e0a\u9762\u7684\u70b9\uff0c\u6807\u5fd7\u7740\u8fd9\u4e2a\u5b50\u56fe\u5df2\u7ecf\u5904\u7406\u5b8c\u6bd5*<\/p>\n

    \u6211\u4eec\u5728\u521d\u59cb\u5316\u65f6\uff0c\u5c06DFN\u6570\u7ec4\u5168\u90e8\u7f6e\u4e3a0\u8868\u793a\u6ca1\u6709\u8bbf\u95ee\u8fc7\uff0c\u4e3a\u4e86\u9632\u6b62\u56fe\u4e0d\u8fde\u901a\uff0c\u4e3b\u7a0b\u5e8f\u5199\u6210\u8fd9\u6837\uff1a<\/p>\n

    memset(dfn,0,sizeof(dfn));\nmemset(v,false,sizeof(v));\/\/v\u6570\u7ec4\u7528\u6765\u8ddf\u8e2a\u662f\u5426\u5728\u6808\u91cc\nfor(int i=1;i<=n;i++)\n    if(!dfn[i]) tarjan(i);<\/code><\/pre>\n
    \u73b0\u5728\u53ef\u4ee5\u5199\u5b50\u7a0b\u5e8f\u4e86<\/p>\n
    void tarjan(int x)\n{\n   dfn[x]=low[x]=++tmmk;\/\/time mark\n   S.push(x);\n   v[x]=true;\n   for(int i=head[x];i;i=next[i])\n   {\n     int y=E[i].dot;\n     if(!dfn[y])\n     {\n       tarjan(y);\n       low[x]=min(low[x],low[y]);\n     }\n     else\n       if(v[y])\n          low[x]=min(low[x],dfn[y]);\n   }\n   if(dfn[x]==low[x])\n   {\n      ans++;\n      int y;\n      do{\n        y=S.top();\n        S.pop();\n        v[y]=false;\n        col[y]=ans;\n        g[ans].push_back(y);\n        \/*\n        \u8fd9\u91cc\u5904\u7406\u4e86\u6bcf\u4e2a\u7ed3\u679c\n        *\/\n      }while(y!=x)\n   }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u5148\u4ecb\u7ecd\u51e0\u4e2a\u57fa\u672c\u6982\u5ff5\uff1a \u5f3a\u8fde\u901a\uff1a \u5728\u4e00\u4e2a\u6709\u5411\u56feG\u91cc\uff0c\u8bbe\u4e24\u4e2a\u70b9 a b\uff0c\u7531a\u6709\u4e00\u6761\u8def […]<\/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-404","post","type-post","status-publish","format-standard","hentry","category-2"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/404","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=404"}],"version-history":[{"count":1,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/404\/revisions"}],"predecessor-version":[{"id":740,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/404\/revisions\/740"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}