{"id":977,"date":"2019-11-14T22:33:27","date_gmt":"2019-11-14T14:33:27","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=977"},"modified":"2019-11-14T22:33:27","modified_gmt":"2019-11-14T14:33:27","slug":"lp3225-hnoi2012-%e7%9f%bf%e5%9c%ba%e6%90%ad%e5%bb%ba","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/11\/14\/lp3225-hnoi2012-%e7%9f%bf%e5%9c%ba%e6%90%ad%e5%bb%ba\/","title":{"rendered":"lp3225 HNOI2012 \u77ff\u573a\u642d\u5efa"},"content":{"rendered":"\n<p><\/p>\n\n\n\n<p>\u8fd9\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a Tarjan \u6c42\u5272\u70b9\u7684\u88f8\u9898\u3002<\/p>\n\n\n\n<p>\u5177\u4f53\u6765\u8bf4\u662f\u8fd9\u6837\u7684\u3002\u9996\u5148\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8fde\u901a\u5757\uff0c\u7b54\u6848\u663e\u7136\u662f\u72ec\u7acb\u7684\u3002\u7136\u540e\uff0c\u4e00\u4e2a\u8fde\u901a\u5757\u81f3\u5c11\u8981\u6709\u4e24\u4e2a\u51fa\u53e3\u2014\u2014\u8fd9\u4e5f\u662f\u5bb9\u6613\u7406\u89e3\u7684\u3002<\/p>\n\n\n\n<p>\u63a5\u4e0b\u6765\uff0c\u6211\u4eec\u628a\u6240\u6709\u70b9\u53cc\u90fd\u7f29\u6210\u4e00\u4e2a\u70b9\uff0c\u8fd9\u65f6\u5019\u6574\u5f20\u56fe\u5c31\u4e00\u5b9a\u662f\u4e00\u68f5\u65e0\u6839\u6811\u3002<\/p>\n\n\n\n<p>\u6211\u4eec\u89c2\u5bdf\u8fd9\u68f5\u6811\u3002\u5982\u679c\u6811\u4e0a\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\uff0c\u90a3\u4e48\u4e24\u4e2a\u51fa\u53e3\u5c31\u90fd\u5fc5\u987b\u8bbe\u5728\u8fd9\u4e2a\u70b9\u53cc\u4e2d\uff1b\u5982\u679c\u6811\u4e0a\u6709\u591a\u4e2a\u8282\u70b9\uff0c\u90a3\u4e48\u6709\u4e14\u4ec5\u6709\u53f6\u5b50\u8282\u70b9\u8981\u5404\u81ea\u8bbe\u4e00\u4e2a\u51fa\u53e3\uff1a\u8fd9\u662f\u56e0\u4e3a\uff0c\u5bf9\u4e8e\u975e\u53f6\u5b50\u8282\u70b9\uff0c\u5b83\u90fd\u6709\u591a\u6761\u8def\u8d70\u5411\u53f6\u5b50\u8282\u70b9\u3002<\/p>\n\n\n\n<p>\u73b0\u5728\u95ee\u9898\u662f\u5982\u4f55\u6c42\u51fa\u8fd9\u68f5\u6811\u3002\u6211\u4eec\u4e0d\u59a8\u7528 Tarjan \u6765\u6c42\u3002<\/p>\n\n\n\n<p>Tarjan \u662f\u4e00\u79cd\u7528\u4e8e\u6c42\u70b9\u53cc\u8054\u901a\u5206\u91cf\u7684\u5e38\u7528\u7b97\u6cd5\uff0c\u4ee5\u5176\u53d1\u660e\u8005 Tarjan \u6240\u547d\u540d\u3002\u7279\u522b\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u8fd9\u91cc\u7528\u5230\u7684\u662f  Tarjan \u6c42\u5272\u70b9\u7684\u90e8\u5206\uff0c\u800c\u4e0d\u662f\u50cf\u5706\u65b9\u6811\u90a3\u6837\u6c42\u70b9\u53cc\u7684\u90e8\u5206\u3002<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u4e00\u4e2a\u70b9\uff0c\u6211\u4eec\u8bb0\u4e24\u4e2a\u6570\u7ec4\uff0cdfn \u548c lw\uff0c\u5206\u522b\u8868\u793a\u5b83\u7684 dfs \u5e8f\u548c\u5b83\u5728 dfs \u6811\u7684\u5b50\u6811\u5185\u7684\u6240\u6709\u8282\u70b9\u7684\u8fd4\u7956\u8fb9\u4e2d dfs \u6700\u5c0f\u7684\u8282\u70b9\u3002<\/p>\n\n\n\n<p>\u5982\u679c\u67d0\u4e00\u4e2a\u8282\u70b9\uff0c\u5b83\u662f\u6839\u8282\u70b9\uff0c\u5e76\u4e14\u5b83\u5728 dfs \u6811\u4e0a\u6709\u8d85\u8fc7\u4e00\u4e2a\u5b50\u8282\u70b9\uff0c\u90a3\u4e48\u5b83\u5fc5\u7136\u662f\u5272\u70b9\u2014\u2014\u8fd9\u662f\u7531 dfs \u6811\u7684\u6027\u8d28\u51b3\u5b9a\u7684\u3002<\/p>\n\n\n\n<p>\u5982\u679c\u4e00\u4e2a\u8282\u70b9\uff0c\u5b83\u7684\u5b50\u8282\u70b9\u7684 lw \u603b\u662f\u5927\u7b49\u4e8e\u5b83\u7684 dfn \uff0c\u90a3\u4e48\u5c31\u8bf4\u660e\u5b83\u7684\u8fd9\u68f5\u5b50\u6811\u5185\u7684\u6240\u6709\u8282\u70b9\u53ea\u80fd\u62b5\u8fbe\u5b83\u6216\u8005\u5b83\u5b50\u6811\u5185\u7684\u70b9\uff0c\u56e0\u800c\u5b83\u5fc5\u7136\u662f\u5272\u70b9\u3002<\/p>\n\n\n\n<p>\u7ed3\u5408\u8fd9\u4e24\u6761\u6027\u8d28\u5373\u53ef\u627e\u51fa\u70b9\u53cc\u3002<\/p>\n\n\n\n<p>\u7136\u540e\u7edf\u8ba1\u4e00\u4e0b\u5373\u53ef\u3002\u5b58\u5728\u4e00\u5b9a\u7684\u7ec6\u8282\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cstring>\n#include&lt;algorithm>\n#include&lt;queue>\n#include&lt;vector>\nusing namespace std;\ntypedef long long ll;\nconst int N=505;\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N&lt;&lt;2];\nstruct Data{\n\tint u;int v;\n}lst[N&lt;&lt;2];\nint g[N],h[N],et=0;\ninline void Eadd(int U,int V,int *H){\n\te[++et]=(ee){V,H[U]};\n\tH[U]=et;\n}\ninline void add(int U,int V,int *H){\n\tEadd(U,V,H);\n\tEadd(V,U,H);\n}\nint n;\nint dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];\ninline void dfs0(int X,int FA){\n\tdfn[X]=lw[X]=++dfsid;sn[X]=0;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(e[i].v==FA){\n\t\t\tcontinue;\n\t\t}\n\t\tif(!dfn[e[i].v]){\n\t\t\t++sn[X];\n\t\t\tdfs0(e[i].v,X);\n\t\t\tlw[X]=min(lw[X],lw[e[i].v]);\n\t\t\tif((FA&amp;&amp;lw[e[i].v]>=dfn[X])){\n\t\t\t\tag[X]=1;\n\t\t\t}\n\t\t}else{\n\t\t\tlw[X]=min(lw[X],dfn[e[i].v]);\n\t\t}\n\t}\n\tif(!FA&amp;&amp;sn[X]>1){\n\t\tag[X]=1;\n\t}\n}\nll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];\ninline void dfs1(int X){\n\tvis[X]=nv;++sz;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(vis[e[i].v]==nv){\n\t\t\tcontinue;\n\t\t}\n\t\tif(ag[e[i].v]){\n\t\t\tvis[e[i].v]=nv;++cal;\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v);\n\t}\n}\nll ans,cans,nt;\nvoid init(){\n\tcnt=et=dfsid=nt=0;\n\tfor(int i=1;i&lt;=n;++i){\n\t\th[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;\n\t}\n\tint u,v;\n\tfor(int i=1;i&lt;=n;++i){\n\t\tscanf(\"%d%d\",&amp;u,&amp;v);\n\t\tadd(u,v,h);\n\t\t++deg[u];++deg[v];\n\t\tlst[i]=(Data){u,v};\n\t\tnt=max(nt,1ll*u);nt=max(nt,1ll*v);\n\t}\n\tfor(int i=1;i&lt;=nt;++i){\n\t\tif(!dfn[i]){\n\t\t\tdfs0(i,0);\n\t\t}\n\t}\n\/\/\tfor(int i=1;i&lt;=nt;++i){\n\/\/\t\tprintf(\"%d \",ag[i]);\n\/\/\t}\n\/\/\tputs(\"\");\n\tans=0,cans=1;\n\tfor(int i=1;i&lt;=nt;++i){\n\t\tif(ag[i]){\n\t\t\tif(deg[i]&lt;=1){\n\t\t\t\t++ans;\n\t\t\t}\n\t\t}else if(!vis[i]){\n\t\t\tnv=i;cal=0;sz=0;\n\t\t\tdfs1(i);\n\t\t\tif(cal==1){\n\t\t\t\t++ans;cans*=sz;\n\t\t\t}else if(cal==0){\n\t\t\t\tans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)\/2);\n\t\t\t}\n\t\t}\n\t}\n}\nint main(){\n\tscanf(\"%d\",&amp;n);\n\tint T=0;\n\twhile(n){\n\t\t++T;\n\t\tinit();\n\t\tprintf(\"Case %d: %lld %lld\\n\",T,ans,cans);\n\t\tscanf(\"%d\",&amp;n);\n\t}\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u8fd9\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a Tarjan \u6c42\u5272\u70b9\u7684\u88f8\u9898\u3002 \u5177\u4f53\u6765\u8bf4\u662f\u8fd9\u6837\u7684\u3002\u9996\u5148\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8fde\u901a\u5757\uff0c\u7b54\u6848\u663e\u7136\u662f\u72ec\u7acb\u7684\u3002\u7136\u540e &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2019\/11\/14\/lp3225-hnoi2012-%e7%9f%bf%e5%9c%ba%e6%90%ad%e5%bb%ba\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp3225 HNOI2012 \u77ff\u573a\u642d\u5efa\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[112,128,30,56,103,9,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/977"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=977"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/977\/revisions"}],"predecessor-version":[{"id":978,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/977\/revisions\/978"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=977"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}