\u70b9<\/span><\/strong>,\u6bd4\u8f83\u7279\u6b8a,\u662flogN)<\/p>\n\u4fee\u6539(Insert)\u65f6\u7531\u9876\u800c\u4e0b\u4ee5\u7c7b\u4f3c\u4e8c\u5206\u7684\u65b9\u6cd5\u627e\u5230\u6700\u4e0b\u9762\uff0c\u7136\u540e\u56de\u6eaf\uff0c\u6bd4\u8f83\u521a\u66f4\u65b0\u7684\u70b9\u4e0e\u53e6\u4e00\u5b50\u6811\uff0c\u6c42Min\uff0c\u66f4\u65b0\u4e3a\u5f53\u524d\u7ebf\u6bb5\u7684Min\u503c
\n\u8fd9\u4e2a\u6a21\u578b\u6bd4\u67d3\u8272\u7528\u7684\u7ebf\u6bb5\u6811\u7b80\u5355\u591a\u4e86\uff0c\u4e8e\u662f\u5b83\u6210\u4e86\u6211\u7ebf\u6bb5\u6811AC\u7b2c\u4e00\u9898(\u8bdd\u8bf4\u5728\u673a\u623f\u503c\u65e5\u7684\u611f\u89c9~~\u723d\uff01)<\/p>\n
\u8d34\u4e4b\u4ee3\u7801:
\n<\/p>\n
\/*\r\nProblem: 1236\t\tUser: comzyh\r\nMemory: 240K\t\tTime: 0MS\r\nLanguage: C++\t\tResult: Accepted\r\n*\/\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <cstdlib>\r\nint tab[101][101];\r\nint DFN[101],LOW[101],stack[200],instack[200];\r\nint f[101];\r\nint belong[101];\r\nint top,RB,RT;\/\/\u6808\u9876,\u6700\u540e\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u7f16\u53f7,\u6700\u540e\u4e00\u4e2a\u65f6\u95f4\u6233 \r\nint ein[101],eout[101],ans,ans1,ans2;\r\nint N;\r\n\/\/Function\r\nvoid Tarjan(int x);\r\nint getf(int x);\r\ninline void add(int x,int y);\/\/add x to y\r\nint main()\r\n{\r\n int i,j,to;\r\n scanf(\"%d\",&N);\r\n memset(tab,0,sizeof(tab));\r\n for (i=1;i<=N;i++)\r\n while (scanf(\"%d\",&to),to)\r\n tab[i][++tab[i][0]]=to;\r\n \/\/\r\n memset(DFN,0,sizeof(DFN));\r\n memset(instack,0,sizeof(instack));\r\n top=RB=RT=0;\r\n for (i=1;i<=N;i++)\r\n f[i]=i;\r\n for (i=1;i<=N;i++)\r\n if (!DFN[i])\r\n Tarjan(i);\r\n \/\/for (i=1;i<=N;i++)printf(\"%4d belong to %4d\\n\",i,belong[i]);\r\n memset(ein,0,sizeof(ein));\r\n memset(eout,0,sizeof(eout));\r\n for (i=1;i<=N;i++)\r\n if (tab[i][0])\r\n {\r\n eout[belong[i]]=1;\r\n for (j=1;j<=tab[i][0];j++)\r\n if (getf(i)!= getf(tab[i][j]))ein[belong[tab[i][j]]]=1;\r\n }\r\n ans1=ans2=0;\r\n for (i=1;i<=RB;i++)\r\n {\r\n if (!ein[i] )ans1++;\r\n if (!eout[i])ans2++;\r\n }\r\n ans=(ans1>ans2)?ans1:ans2;\r\n if (RB==1)ans=0;\/\/\u5982\u679c\u5c31\u4e00\u4e2a\u5206\u91cf,\u663e\u7136\u4e0d\u7528\u518d\u8fde\u63a5 \r\n printf(\"%d\\n%d\",ans1,ans);\r\n system(\"pause\");\r\n}\r\nvoid Tarjan(int x)\r\n{\r\n int i,t;\/\/t= top \/ to \u591a\u7528\u9014, \r\n stack[++top]=x;\r\n DFN[x]=LOW[x]=++RT;\r\n instack[x]=1;\r\n for (i=1;i<=tab[x][0];i++)\r\n {\r\n t=tab[x][i];\r\n if (!DFN[t])\r\n {\r\n Tarjan(t);\r\n if (LOW[t] < LOW[x])\r\n LOW[x] = LOW[t];\r\n }\r\n else\r\n if (instack[t] && DFN[t]<LOW[x])\r\n LOW[x]=DFN[t];\r\n }\r\n if (LOW[x] == DFN[x])\r\n {\r\n RB++;\r\n do\r\n {\r\n t=stack[top--];\r\n add(t,x);\r\n belong[t]=RB;\r\n instack[t]=0;\r\n }while(t != x);\r\n }\r\n}\r\nint getf(int x)\r\n{\r\n if (f[x] == x)return x;\r\n else return f[x]=getf(f[x]);\r\n}\r\ninline void add(int x,int y)\/\/add x to y\r\n{\r\n int fx=getf(x),fy=getf(y);\r\n if (fx == fy)return ;\r\n f[fx]=fy;\r\n}<\/pre>\n\u9898\u76ee\u5728\u8fd9\u91cc,\u70b9\u4e0b\u7bad\u5934\u5c55\u5f00\u3002<\/p>\n
\u63cf\u8ff0 Description\r\n \u8001\u7ba1\u5bb6\u662f\u4e00\u4e2a\u806a\u660e\u80fd\u5e72\u7684\u4eba\u3002\u4ed6\u4e3a\u8d22\u4e3b\u5de5\u4f5c\u4e86\u6574\u657410\u5e74\uff0c\u8d22\u4e3b\u4e3a\u4e86\u8ba9\u81ea\u5df2\u8d26\u76ee\u66f4\u52a0\u6e05\u695a\u3002\u8981\u6c42\u7ba1\u5bb6\u6bcf\u5929\u8bb0k\u6b21\u8d26\uff0c\u7531\u4e8e\u7ba1\u5bb6\u806a\u660e\u80fd\u5e72\uff0c\u56e0\u800c\u7ba1\u5bb6\u603b\u662f\u8ba9\u8d22\u4e3b\u5341\u5206\u6ee1\u610f\u3002\u4f46\u662f\u7531\u4e8e\u4e00\u4e9b\u4eba\u7684\u6311\u62e8\uff0c\u8d22\u4e3b\u8fd8\u662f\u5bf9\u7ba1\u5bb6\u4ea7\u751f\u4e86\u6000\u7591\u3002\u4e8e\u662f\u4ed6\u51b3\u5b9a\u7528\u4e00\u79cd\u7279\u522b\u7684\u65b9\u6cd5\u6765\u5224\u65ad\u7ba1\u5bb6\u7684\u5fe0\u8bda\uff0c\u4ed6\u628a\u6bcf\u6b21\u7684\u8d26\u76ee\u63091\uff0c2\uff0c3\u2026\u7f16\u53f7\uff0c\u7136\u540e\u4e0d\u5b9a\u65f6\u7684\u95ee\u7ba1\u5bb6\u95ee\u9898\uff0c\u95ee\u9898\u662f\u8fd9\u6837\u7684\uff1a\u5728a\u5230b\u53f7\u8d26\u4e2d\u6700\u5c11\u7684\u4e00\u7b14\u662f\u591a\u5c11\uff1f\u4e3a\u4e86\u8ba9\u7ba1\u5bb6\u6ca1\u65f6\u95f4\u4f5c\u5047\u4ed6\u603b\u662f\u4e00\u6b21\u95ee\u591a\u4e2a\u95ee\u9898\u3002\r\n\u3000\u3000\u5728\u8be2\u95ee\u8fc7\u7a0b\u4e2d\u8d26\u672c\u7684\u5185\u5bb9\u53ef\u80fd\u4f1a\u88ab\u4fee\u6539\r\n\u8f93\u5165\u683c\u5f0f Input Format\r\n \u8f93\u5165\u4e2d\u7b2c\u4e00\u884c\u6709\u4e24\u4e2a\u6570m,n\u8868\u793a\u6709m(m<=100000)\u7b14\u8d26,n\u8868\u793a\u6709n\u4e2a\u95ee\u9898\uff0cn<=100000\u3002\r\n\u63a5\u4e0b\u6765\u6bcf\u884c\u4e3a3\u4e2a\u6570\u5b57\uff0c\u7b2c\u4e00\u4e2ap\u4e3a\u6570\u5b571\u6216\u6570\u5b572\uff0c\u7b2c\u4e8c\u4e2a\u6570\u4e3ax\uff0c\u7b2c\u4e09\u4e2a\u6570\u4e3ay\r\n\u5f53p=1 \u5219\u67e5\u8be2x,y\u533a\u95f4\r\n\u5f53p=2 \u5219\u6539\u53d8\u7b2cx\u4e2a\u6570\u4e3ay\r\n\u8f93\u51fa\u683c\u5f0f Output Format\r\n \t\u8f93\u51fa\u6587\u4ef6\u4e2d\u4e3a\u6bcf\u4e2a\u95ee\u9898\u7684\u7b54\u6848\u3002\u5177\u4f53\u67e5\u770b\u6837\u4f8b\u3002\r\n\u6837\u4f8b\u8f93\u5165 Sample Input\r\n10 3\r\n1 2 3 4 5 6 7 8 9 10\r\n1 2 7\r\n2 2 0\r\n1 1 10\r\n\u6837\u4f8b\u8f93\u51fa Sample Output\r\n2 0\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u5173\u4e8e\u9759\u6001\u4e0d\u4fee\u6539\u5143\u7d20\u7684O(1)\u67e5\u8be2\u7684RMQ (Range Minimum\/Maximum Query)\u7b97\u6cd5\u533a\u95f4\u6700 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[11,9],"tags":[41,44],"class_list":["post-377","post","type-post","status-publish","format-standard","hentry","category-programing","category-9","tag-rmq","tag-44"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-65","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/377","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=377"}],"version-history":[{"count":2,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/377\/revisions"}],"predecessor-version":[{"id":863,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/377\/revisions\/863"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=377"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=377"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=377"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}