{"id":406,"date":"2022-10-06T20:51:32","date_gmt":"2022-10-06T12:51:32","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=406"},"modified":"2022-10-06T20:51:32","modified_gmt":"2022-10-06T12:51:32","slug":"%e9%a2%98%e8%a7%a3-p1726-%e3%80%90%e4%b8%8a%e7%99%bd%e6%b3%bd%e6%85%a7%e9%9f%b3%e3%80%91","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=406","title":{"rendered":"\u9898\u89e3 P1726 \u3010\u4e0a\u767d\u6cfd\u6167\u97f3\u3011"},"content":{"rendered":"<p>\u8bf4\u5728\u524d\u9762\uff1a\u65e2\u7136\u662f\u6ca1\u4ec0\u4e48\u5305\u88c5\u7684\u6a21\u677f\u9898\uff0c\u90a3\u4e48\u5efa\u8bae\u5927\u5bb6\u6253\u7ec6\u81f4\u4e00\u4e9b\uff0c\u5982\u679c\u4e0d\u5f88\u6e05\u695a\uff0c\u4ee3\u7801\u91cf\u591a\u4e00\u4e9b\u4e5f\u6ca1\u5173\u7cfb\uff0c\u4e00\u6761\u4e00\u6761\u91cd\u5728\u7406\u89e3\u900f\u5f7b<\/p>\n<hr \/>\n<p>\u597d\uff0c\u8fdb\u5165\u6b63\u9898\uff1a<\/p>\n<p>\u5f88\u660e\u663e\u7684\u4e00\u9053Tarjan\uff0c\u9898\u89e3\u4e2d\u8bb2Tarjan\u7684\u795e\u7287\u4e5f\u6709\u5f88\u591a\uff0c\u4f46\u662f\u6211\u81ea\u8ba4\u4e3a\u8fd8\u53ef\u4ee5\u591a\u7528\u4e9b\u56fe\u548cMarkdown\u5c06\u8fd9\u4e2a\u7b97\u6cd5\u8bb2\u7684\u66f4\u6e05\u695a\u4e9b\uff0c\u6240\u4ee5\u8fd9\u91cc\u91cd\u65b0\u8bb2\u4e00\u4e0bTarjan\uff1a<\/p>\n<hr \/>\n<p>\u8fd9\u91cc\u666e\u53ca\u57fa\u672c\u6982\u5ff5:<\/p>\n<ul>\n<li>\u5f3a\u8fde\u901a\u5206\u91cf\uff1a\u5bf9\u4e8e\u56feG\u6765\u8bf4\u7684\u4e00\u4e2a\u5b50\u56fe\u4e2d\uff0c\u4efb\u610f\u4e24\u4e2a\u70b9\u90fd\u53ef\u4ee5\u5f7c\u6b64\u5230\u8fbe\uff0c\u8fd9\u4e2a\u5b50\u56fe\u5c31\u88ab\u79f0\u4e3a\u56feG\u7684\u8fde\u901a\u5206\u91cf\uff08\u4e00\u4e2a\u70b9\u5c31\u662f\u6700\u5c0f\u7684\u8fde\u901a\u5206\u91cf\uff09<\/li>\n<li>\u65f6\u95f4\u6233\uff1a\u641c\u7d22\u5230\u4e00\u4e2a\u70b9\u65f6\uff0c\u8fd9\u4e2a\u70b9\u5c06\u88ab\u8d4b\u4e88\u4e00\u4e2a <em>\u552f\u4e00<\/em> \u7684\u65f6\u95f4\u91cf\uff0c\u5e76\u4e14\u8d8a\u65e9\u641c\u5230\u7684\u70b9\u65f6\u95f4\u6233\u8d8a\u5c0f\uff08\u5f53\u7136\u4e86\uff09 <\/li>\n<\/ul>\n<p>Tarjan\u662f\u4e00\u4e2a\u57fa\u4e8e\u6df1\u641c\uff0c\u53ef\u4ee5\u6c42\u89e3\u56fe\u4e2d\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u7684\u7b97\u6cd5\uff0c\u57fa\u672c\u601d\u60f3\u8bf7\u770b\u56fe\uff1a<\/p>\n<p>\u5728\u6211\u4eec\u5bf9\u4e00\u4e2a\u56fe\u8fdb\u884c\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u65f6\uff0c\u8d70\u8fc7\u7684\u8fb9\u4f1a\u5f97\u5230\u4e00\u68f5\u641c\u7d22\u6811\uff0c\u641c\u7d22\u6811\u53ef\u4ee5\u770b\u505a\u662f\u539f\u56fe\u629b\u5f03\u4e86\u4e00\u4e9b\u8fb9\u800c\u5f62\u6210\u7684<\/p>\n<p>\u8fd9\u4fbf\u662f\u4e00\u68f5\u641c\u7d22\u6811\u4e86<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/cdn.luogu.com.cn\/upload\/pic\/63447.png\" alt=\"\" \/><\/p>\n<p>\u6211\u4eec\u5bf9\u629b\u5f03\u6389\u7684\u8fb9\u505a\u4e00\u4e2a\u5206\u7c7b\uff0c\u5bf9\u4e8e\u8fd9\u68f5\u6811\u4e2d\u88ab\u8fd8\u539f\u7684\u539f\u56fe\u4e2d\u7684\u8fb9\u6709\u4e09\u79cd\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/cdn.luogu.com.cn\/upload\/pic\/63515.png\" alt=\"\" \/><\/p>\n<ul>\n<li>\u7ea2\u8272\u7684\u8fb9-\u6a2a\u53c9\u8fb9<\/li>\n<li>\u84dd\u8272\u7684\u8fb9-\u524d\u5411\u8fb9<\/li>\n<li>\u7eff\u8272\u7684\u8fb9-\u540e\u5411\u8fb9<\/li>\n<\/ul>\n<p>\u4e0d\u96be\u53d1\u73b0\uff0c\u6a2a\u53c9\u8fb9\u548c\u524d\u5411\u8fb9\u90fd\u65e0\u6cd5\u6784\u6210\u56de\u8def\uff0c\u5373\u4e0d\u80fd\u5f62\u6210\u5927\u4e8e\u4e00\u4e2a\u70b9\u7684\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u6240\u4ee5\u6211\u4eec\u8981\u505a\u7684\uff0c\u5c31\u662f\u627e\u51fa\u91cd\u8981\u7684\u540e\u5411\u8fb9\u6765<\/p>\n<p>\u600e\u4e48\u627e\u540e\u5411\u8fb9\u5462\uff1f\u4f60\u53ef\u4ee5\u56de\u60f3\u4e00\u4e0b\u521a\u624d\u63d0\u5230\u7684\u201c\u65f6\u95f4\u6233\u201d\uff0c\u6ca1\u9519\uff0c\u5982\u679c\u6211\u4eec\u641c\u7d22\u5230\u4e86\u4e00\u4e2a<strong>\u4e4b\u524d\u641c\u8fc7\u7684\u70b9\uff0c\u4e14\u4ed6\u5f53\u524d\u70b9\u7684\u7956\u5148\u4e00\u6837\uff0c\u90a3\u4e48\u6beb\u65e0\u7591\u95ee\u7684\uff0c\u6211\u4eec\u8d70\u5728\u4e86\u540e\u5411\u8fb9\u4e0a<\/strong><\/p>\n<p>Tarjan\u7b97\u6cd5\u4f7f\u7528\u4e24\u4e2a\u6570\u7ec4\u6765\u7ef4\u62a4\u8fd9\u4e2a\u4fe1\u606f\uff1a<\/p>\n<ul>\n<li>dfn[maxn]:\u50a8\u5b58\u6bcf\u4e2a\u70b9\u7684\u65f6\u95f4\u6233<\/li>\n<li>low[maxn]:\u50a8\u5b58\u6bcf\u4e2a\u70b9\u8bbf\u95ee\u7956\u5148\u7684\u80fd\u529b<\/li>\n<\/ul>\n<p>\u4ec0\u4e48\u662f\u8bbf\u95ee\u7956\u5148\u7684\u80fd\u529b\u5462\uff1f\u5c31\u662f\u8bf4\uff0c\u8fd9\u4e2a\u70b9\u6700\u591a\u80fd\u8d70\u56de\u5934\u8def\u5230\u4ec0\u4e48\u5730\u6b65\uff0clow\u6570\u7ec4\u50a8\u5b58\u7684\u662f\u4ed6\u80fd\u8bbf\u95ee\u5230\u7684\u6700\u65e9\u7956\u5148\u7684dfn\u503c\uff0c\u5982\u679c\u8fd9\u4e2a\u70b9\u6ca1\u6709\u56de\u5934\u8def\u53ef\u8d70\uff0c\u90a3low\u503c\u5c31\u662f\u4ed6\u81ea\u5df1\u7684dfn\u503c\u54af<\/p>\n<p>\u597d\u4e86\uff0c\u8bf4\u4e86\u8fd9\u4e48\u591a\uff0c\u76f8\u4fe1\u4f60\u5df2\u7ecf\u6709\u4e00\u4e9b\u611f\u89c9\u4e86\uff0c\u6211\u4eec\u6765\u770bTarjan\u7684\u6a21\u677f\u4ee3\u7801\uff1a<\/p>\n<pre><code class=\"language-cpp\">struct edge{\n    int x,y,w;\n}E[maxm];\nint dfn[maxn],low[maxn],tmmk=0;\nbool v[maxn];\/\/v\u6570\u7ec4\u7528\u6765\u8ddf\u8e2a\u8fd9\u4e2a\u70b9\u662f\u5426\u5df2\u7ecf\u5904\u7406\u5b8c\u6bd5\uff0c\u6211\u4eec\u7a0d\u540e\u4f1a\u89c1\u5230\u5b83\u7684\u7528\u6cd5\nstack&lt;int&gt; S;\nvoid tarjan(int x)\n{\n   dfn[x]=low[x]=++tmmk;\/\/\u6bcf\u4e2a\u70b9\u5728\u6700\u5f00\u59cb\u88ab\u8bbf\u95ee\u65f6\uff0c\u65f6\u95f4\u6233\u548clow\u503c\u90fd\u662f\u4e00\u6837\u7684\n   S.push(x);\n   v[x]=true;\n   for(int i=head[x];i;i=next[i])\/\/\u94fe\u5f0f\u524d\u5411\u661f\u67e5\u90bb\u63a5\u70b9\n   {\n     int y=E[i].y;\/\/\u4e0d\u719f\u6089\u7684\u540c\u5b66\u8bf7\u50cf\u8fd9\u6837\u6253\u591a\u4e00\u70b9\uff0c\u6709\u52a9\u4e8e\u7406\u89e3\n     if(!dfn[y])\/\/dfn\u7684\u521d\u503c\u90fd\u662f0\uff0c\u5982\u679c\u8fd9\u4e2a\u70b9\u6ca1\u6709\u641c\u8fc7\uff0c\u5c31\u9012\u5f52\u641c\u7d22\n     {\n       tarjan(y);\n       low[x]=min(low[x],low[y]);\/\/\u6b64\u65f6\u641c\u7d22\u5df2\u7ecf\u56de\u6eaf\uff0c\u6211\u4eec\u53ef\u4ee5\u786e\u5b9ay\u7684low\u503c\u5df2\u7ecf\u66f4\u6b63\uff0c\u6240\u4ee5\u7528\u5b83\u6765\u66f4\u65b0x\u7684\n     }\/\/\u56e0\u4e3ay\u5728x\u7684\u540e\u9762\uff0c\u6240\u4ee5y\u80fd\u8bbf\u95ee\u5230\u7684\u7956\u5148x\u4e00\u5b9a\u53ef\u4ee5\u8bbf\u95ee\u5230\n     else\n       if(v[y])\/\/\u5982\u679cy\u70b9\u641c\u8fc7\u4e86\u4e14\u5728\u6808\u91cc\uff0c\u8bf4\u660e\u6211\u4eec\u627e\u5230\u4e86 \u540e\uff01\u5411\uff01\u8fb9\uff01\n          low[x]=min(low[x],dfn[y]);\n   }\/\/\u4f46\u662f\u6b64\u65f6\u6211\u4eec\u8fd8\u4e0d\u80fd\u6025\u7740\u5904\u7406\uff0c\u4e3a\u4ec0\u4e48\uff1f\u56e0\u4e3a\u6709\u56de\u6eaf\u5230\u6839\u4e86\u4ee5\u540e\u6211\u4eec\u5728\u6536\u96c6\u5230\u4e86\u5b8c\u6574\u7684\u4fe1\u606f\n   if(dfn[x]==low[x])\n   {\/\/dfn\u548clow\u4e00\u6837\uff0c\u4f60\u5c31\u662f\u4e0e\u4f17\u4e0d\u540c\u7684\u6839\u8282\u70b9\n      ans++;\/\/ans\u662f\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u4e2a\u6570\n      int y;\n      do{\n        y=S.top();\n        S.pop();\n        v[y]=false;\n        col[y]=ans;\/\/y\u70b9\u5c5e\u4e8e\u7f16\u53f7\u4e3aans\u7684\u5f3a\u8fde\u901a\u5206\u91cf\n        g[ans].push_back(y);\/\/\u5b58\u4e0b\u6bcf\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u7684\u6210\u5458\n      }while(y!=x)\/\/\u5728\u8fd9\u91cc\u5c06\u6808\u91cc\u7684\u70b9\u5168\u90e8\u5012\u51fa\u6765\uff08\u5012\u5783\u573e\u4e00\u6837..\uff09\n   }\n}<\/code><\/pre>\n<hr \/>\n<p>\u56de\u5230\u9898\u76ee\uff01<\/p>\n<p>\u9898\u76ee\u8981\u6c42\u6c42\u51fa\u56fe\u4e2d\u6700\u5927\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u548c\u5176\u4e2d\u6240\u6709\u7684\u70b9<\/p>\n<p>\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\uff0c\u4ee5\u4e0a\u6a21\u677f\u4e2dcol\u6570\u7ec4\u7528\u4e0d\u7740\u4e86\uff0c\u5b58\u6210\u5458\u8fd8\u662f\u5fc5\u8981\u7684\uff0c\u4f46\u662f\u8981\u6c42\u5b57\u5178\u5e8f\u8f93\u51fa\uff0c\u8fd9\u4e2a\u5411\u91cf\u5c31\u4e0d\u5f88\u65b9\u4fbf\u4e86\uff0c\u6211\u4eec\u53ef\u4ee5\u7528\u4f18\u5148\u961f\u5217\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898<\/p>\n<p>\u5173\u4e8e\u4f18\u5148\u961f\u5217\u7684\u57fa\u672c\u7528\u6cd5\u53ef\u4ee5\u770b\u6211\u535a\u5ba2\uff0c\u8fd9\u91cc\u5173\u7cfb\u4e0d\u5f88\u5927\u4e0d\u505a\u6df1\u7a76qwq<\/p>\n<p>AC\u4ee3\u7801\uff1a\u4e0d\u5f00O2 55ms\uff08\u5077\u61d2\u7528stl\u7684\u4ee3\u4ef7\uff09\u5f00O2 35ms<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/cdn.luogu.com.cn\/upload\/pic\/63445.png\" alt=\"\" \/><\/p>\n<pre><code class=\"language-cpp\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nconst int maxn=6000,maxm=110000;\nint n,m;\n\nint read(){\n    int x=0;char c=getchar();\n    while(c&lt;&#039;0&#039; || c&gt;&#039;9&#039;)c=getchar();\n    while(c&gt;=&#039;0&#039; &amp;&amp; c&lt;=&#039;9&#039;){\n        x=(x&lt;&lt;3)+(x&lt;&lt;1)+(c^&#039;0&#039;);\n        c=getchar();\n    }\n    return x;\n}\n\nint head[maxn],nxt[maxm],id=0;\nstruct edge{\n    int x,y;\n}G[maxm];\nvoid add(int x,int y){\n    G[++id].x=x;\n    G[id].y=y;\n    nxt[id]=head[x];\n    head[x]=id;\n}\n\nstruct pointer{\/\/\u8fd9\u662f\u4e00\u4e2a\u6307\u9488\uff0cp\u6307\u5411\u8fde\u901a\u96c6\u7f16\u53f7\uff0csiz\u662f\u4ed6\u7684\u5927\u5c0f\u65b9\u4fbf\u6392\u5e8f\n    int p,siz=0;\n    int diction;\/\/diction\u662f\u7b2c\u4e00\u4e2a\u70b9\u7684\u7f16\u53f7\uff0c\u5982\u679c\u4e25\u683c\u5b57\u5178\u5e8f\u8bf7\u6539\u6210\u6570\u7ec4\n}p[maxn];\n\nint dfn[maxn],low[maxn],col[maxn],\n    tmmk=0,cnt=0;\nstack&lt;int&gt; S;\npriority_queue&lt;int,vector&lt;int&gt;,greater&lt;int&gt; &gt; g[maxn];\nbool instk[maxn];\nvoid tarjan(int x){\n    dfn[x]=low[x]=++tmmk;\n    S.push(x);\n    instk[x]=true;\n    for(int i=head[x];i;i=nxt[i]){\n        int y=G[i].y;\n        if(!dfn[y]){\n            tarjan(y);\n            low[x]=min(low[x],low[y]);\n        }\n        else if(instk[y])\n            low[x]=min(low[x],dfn[y]);\n    }\n    if(dfn[x]==low[x]){\n        cnt++;\n        int y;\n        p[cnt].diction=S.top();\n        do{\n            y=S.top();\n            S.pop();\n            instk[y]=false;\n            col[y]=cnt;\n            p[cnt].p=cnt;\n            p[cnt].siz++;\n            g[cnt].push(y);\n        }while(y!=x);\n    }\n}\n\nbool cmp(pointer a,pointer b){\n    if(a.siz!=b.siz)\n        return a.siz&gt;b.siz;\n    else\n        return a.diction&lt;b.diction;\n}\n\nint main(){\n    n=read(),m=read();\n\n    int x,y,f;\n    for(int i=1;i&lt;=m;i++){\n        x=read(),y=read(),f=read();\n        add(x,y);\n        if(f==2)\n            add(y,x);\n    }\n\n    memset(dfn,0,sizeof(dfn));\n    memset(instk,false,sizeof(instk));\n    for(int i=1;i&lt;=n;i++)\n        if(!dfn[i])\n            tarjan(i);\n\n    sort(p+1,p+cnt+1,cmp);\n\n    printf(&quot;%d\\n&quot;,p[1].siz);\n    while(!g[p[1].p].empty()){\n        printf(&quot;%d &quot;,g[p[1].p].top());\n        g[p[1].p].pop();\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n<p>PS\uff1a\u672c\u9898\u6570\u636e\u7565\u6c34\uff0c\u9898\u89e3\u4e2d\u6709\u4e9b\u5e76\u6ca1\u6709\u8003\u8651\u5230\u4e00\u822c\u5b57\u5178\u5e8f\u8fd8A\u6389\u7684\uff0c\u5e0c\u671b\u540c\u5b66\u4eec\u6ce8\u610f\u3002\u53e6\uff1a\u6211\u8fd9\u6837\u505a\u4e5f\u53ea\u8003\u8651\u7b2c\u4e00\u4e2a\u6570\u7684\u5b57\u5178\u5e8f\uff0c\u5982\u679c\u4e25\u683c\u6392\u5217\u628a\u5b57\u5178diction\u6539\u6210\u6570\u7ec4\u5373\u53ef<\/p>\n<p>PSPS\uff1a\u5927\u534a\u591c\u5199\u8fd9\u4e2a\u633a\u7d2f\u7684\uff0c\u5982\u679c\u6709\u5e2e\u5230\u4f60\uff0c\u8bf7\u4e0d\u8981\u541d\u60dc\u4f60\u7684\u8d5e\uff08\u7b11\uff09<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u8bf4\u5728\u524d\u9762\uff1a\u65e2\u7136\u662f\u6ca1\u4ec0\u4e48\u5305\u88c5\u7684\u6a21\u677f\u9898\uff0c\u90a3\u4e48\u5efa\u8bae\u5927\u5bb6\u6253\u7ec6\u81f4\u4e00\u4e9b\uff0c\u5982\u679c\u4e0d\u5f88\u6e05\u695a\uff0c\u4ee3\u7801\u91cf [&#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-406","post","type-post","status-publish","format-standard","hentry","category-2"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/406","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=406"}],"version-history":[{"count":0,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/406\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}