{"id":343,"date":"2017-02-17T10:49:58","date_gmt":"2017-02-17T02:49:58","guid":{"rendered":"http:\/\/kylelv.com\/?p=343"},"modified":"2017-12-25T20:38:27","modified_gmt":"2017-12-25T12:38:27","slug":"bzoj-1654-usaco2006-janthe-cow-prom-%e5%a5%b6%e7%89%9b%e8%88%9e%e4%bc%9a-tarjan","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=343","title":{"rendered":"bzoj 1654: [Usaco2006 Jan]The Cow Prom \u5976\u725b\u821e\u4f1a  &#8212; Tarjan"},"content":{"rendered":"<p>&nbsp;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef6cbb362\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdef6cbb362\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#1654_Usaco2006_JanThe_Cow_Prom_%E5%A5%B6%E7%89%9B%E8%88%9E%E4%BC%9A\" title=\"1654: [Usaco2006 Jan]The Cow Prom \u5976\u725b\u821e\u4f1a\">1654: [Usaco2006 Jan]The Cow Prom \u5976\u725b\u821e\u4f1a<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Description\" title=\"Description\">Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Sample_Input\" title=\"Sample Input\">Sample Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Sample_Output\" title=\"Sample Output\">Sample Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#HINT\" title=\"HINT\">HINT<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=343\/#Source\" title=\"Source\">Source<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"1654_Usaco2006_JanThe_Cow_Prom_%E5%A5%B6%E7%89%9B%E8%88%9E%E4%BC%9A\"><\/span>1654: [Usaco2006 Jan]The Cow Prom \u5976\u725b\u821e\u4f1a<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p style=\"text-align: center;\">Time Limit:\u00a05 Sec\u00a0\u00a0Memory Limit:\u00a064 MB<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>The N (2 &lt;= N &lt;= 10,000) cows are so excited: it&#8217;s prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance. Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers. They then acquire a total of M (2 &lt;= M &lt;= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed. For the Round Dance to succeed for any given cow (say, Bessie), the ropes that she holds must be configured just right. To know if Bessie&#8217;s dance is successful, one must examine the set of cows holding the other ends of her ropes (if she has any), along with the cows holding the other ends of any ropes they hold, etc. When Bessie dances clockwise around the tank, she must instantly pull all the other cows in her group around clockwise, too. Likewise, if she dances the other way, she must instantly pull the entire group counterclockwise (anti-clockwise in British English). Of course, if the ropes are not properly distributed then a set of cows might not form a proper dance group and thus can not succeed at the Round Dance. One way this happens is when only one rope connects two cows. One cow could pull the other in one direction, but could not pull the other direction (since pushing ropes is well-known to be fruitless). Note that the cows must Dance in lock-step: a dangling cow (perhaps with just one rope) that is eventually pulled along disqualifies a group from properly performing the Round Dance since she is not immediately pulled into lockstep with the rest. Given the ropes and their distribution to cows, how many groups of cows can properly perform the Round Dance? Note that a set of ropes and cows might wrap many times around the stock tank.<\/p>\n<div>\u00a0\u00a0\u00a0\u00a0\u7ea6\u7ff0\u7684N(2\u2264N\u226410000)\u53ea\u5976\u725b\u975e\u5e38\u5174\u594b\uff0c\u56e0\u4e3a\u8fd9\u662f\u821e\u4f1a\u4e4b\u591c\uff01\u5979\u4eec\u7a7f\u4e0a\u793c\u670d\u548c\u65b0\u978b\u5b50\uff0c\u522b\u4e0a\u9c9c\u82b1\uff0c\u5979\u4eec\u8981\u8868\u6f14\u5706\u821e\uff0e<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u53ea\u6709\u5976\u725b\u624d\u80fd\u8868\u6f14\u8fd9\u79cd\u5706\u821e\uff0e\u5706\u821e\u9700\u8981\u4e00\u4e9b\u7ef3\u7d22\u548c\u4e00\u4e2a\u5706\u5f62\u7684\u6c34\u6c60\uff0e\u5976\u725b\u4eec\u56f4\u5728\u6c60\u8fb9\u7ad9\u597d\uff0c\u987a\u65f6\u9488\u987a\u5e8f\u75311\u5230N\u7f16\u53f7\uff0e\u6bcf\u53ea\u5976\u725b\u90fd\u9762\u5bf9\u6c34\u6c60\uff0c\u8fd9\u6837\u5979\u5c31\u80fd\u770b\u5230\u5176\u4ed6\u7684\u6bcf\u4e00\u53ea\u5976\u725b\uff0e\u4e3a\u4e86\u8df3\u8fd9\u79cd\u5706\u821e\uff0c\u5979\u4eec\u627e\u4e86M(2\u2264M\u226450000)\u6761\u7ef3\u7d22\uff0e\u82e5\u5e72\u53ea\u5976\u725b\u7684\u8e44\u4e0a\u63e1\u7740\u7ef3\u7d22\u7684\u4e00\u7aef\uff0c\u7ef3\u7d22\u6cbf\u987a\u65f6\u9488\u65b9\u7ed5\u8fc7\u6c34\u6c60\uff0c\u53e6\u4e00\u7aef\u5219\u6346\u5728\u53e6\u4e00\u4e9b\u5976\u725b\u8eab\u4e0a\uff0e\u8fd9\u6837\uff0c\u4e00\u4e9b\u5976\u725b\u5c31\u53ef\u4ee5\u7275\u5f15\u53e6\u4e00\u4e9b\u5976\u725b\uff0e\u6709\u7684\u5976\u725b\u53ef\u80fd\u63e1\u6709\u5f88\u591a\u7ef3\u7d22\uff0c\u4e5f\u6709\u7684\u5976\u725b\u53ef\u80fd\u4e00\u6761\u7ef3\u7d22\u90fd\u6ca1\u6709\u5bf9\u4e8e\u4e00\u53ea\u5976\u725b\uff0c\u6bd4\u5982\u8bf4\u8d1d\u831c\uff0c\u5979\u7684\u5706\u821e\u8df3\u5f97\u662f\u5426\u6210\u529f\uff0c\u53ef\u4ee5\u8fd9\u6837\u68c0\u9a8c\uff1a\u6cbf\u7740\u5979\u7275\u5f15\u7684\u7ef3\u7d22\uff0c\u627e\u5230\u5979\u7275\u5f15\u7684\u5976\u725b\uff0c\u518d\u6cbf\u7740\u8fd9\u53ea\u5976\u725b\u7275\u5f15\u7684\u7ef3\u7d22\uff0c\u53c8\u627e\u5230\u4e00\u53ea\u88ab\u7275\u5f15\u7684\u5976\u725b\uff0c\u5982\u6b64\u4e0b\u53bb\uff0c\u82e5\u6700\u7ec8\u80fd\u56de\u5230\u8d1d\u831c\uff0c\u5219\u5979\u7684\u5706\u821e\u8df3\u5f97\u6210\u529f\uff0c\u56e0\u4e3a\u8fd9\u4e00\u4e2a\u73af\u4e0a\u7684\u5976\u725b\u53ef\u4ee5\u9006\u65f6\u9488\u7275\u5f15\u800c\u8df3\u8d77\u65cb\u8f6c\u7684\u571c\u821e\uff0e\u5982\u679c\u8fd9\u6837\u7684\u68c0\u9a8c\u65e0\u6cd5\u5b8c\u6210\uff0c\u90a3\u5979\u7684\u5706\u821e\u662f\u4e0d\u6210\u529f\u7684\uff0e<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u5982\u679c\u4e24\u53ea\u6210\u529f\u8df3\u5706\u821e\u7684\u5976\u725b\u6709\u7ef3\u7d22\u76f8\u8fde\uff0c\u90a3\u5979\u4eec\u53ef\u4ee5\u540c\u5c5e\u4e00\u4e2a\u7ec4\u5408\uff0e<\/div>\n<div>\u00a0\u00a0\u00a0\u00a0\u7ed9\u51fa\u6bcf\u4e00\u6761\u7ef3\u7d22\u7684\u63cf\u8ff0\uff0c\u8bf7\u627e\u51fa\uff0c\u6210\u529f\u8df3\u4e86\u5706\u821e\u7684\u5976\u725b\u6709\u591a\u5c11\u4e2a\u7ec4\u5408\uff1f<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>* Line 1: Two space-separated integers: N and M<\/p>\n<p>* Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.<\/p>\n<div>\u00a0\u00a0\u00a0\u00a0\u7b2c1\u884c\u8f93\u5165N\u548cM\uff0c\u63a5\u4e0b\u6765M\u884c\u6bcf\u884c\u4e24\u4e2a\u6574\u6570A\u548cB\uff0c\u8868\u793aA\u7275\u5f15\u7740B.<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>* Line 1: A single line with a single integer that is the number of groups successfully dancing the Round Dance.<\/p>\n<div>\u00a0\u00a0\u00a0\u00a0\u6210\u529f\u8df3\u5706\u821e\u7684\u5976\u725b\u7ec4\u5408\u6570\uff0e<\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">5 4<br \/>\n2 4<br \/>\n3 5<br \/>\n1 2<br \/>\n4 1INPUT DETAILS:<\/p>\n<p>ASCII art for Round Dancing is challenging. Nevertheless, here is a<br \/>\nrepresentation of the cows around the stock tank:<br \/>\n_1___<br \/>\n\/**** \\<br \/>\n5 \/****** 2<br \/>\n\/ \/**TANK**|<br \/>\n\\ \\********\/<br \/>\n\\ \\******\/ 3<br \/>\n\\ 4____\/ \/<br \/>\n\\_______\/<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>1<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>&nbsp;<\/p>\n<p>1\uff0c2\uff0c4\u8fd9\u4e09\u53ea\u5976\u725b\u540c\u5c5e\u4e00\u4e2a\u6210\u529f\u8df3\u4e86\u5706\u821e\u7684\u7ec4\u5408\uff0e\u800c3\uff0c5\u4e24\u53ea\u5976\u725b\u6ca1\u6709\u8df3\u6210\u529f\u7684\u5706\u821e<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Source\"><\/span>Source<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<pre class=\"lang:c++ decode:true \">#include&lt;cstdio&gt;\r\n#include&lt;iostream&gt;\r\n#define N 10010\r\n#define M 50010\r\nusing namespace std;\r\ninline int min(int a,int b){return a&lt;b?a:b;}\r\ninline int read()\r\n{\r\n    int x=0;char ch=getchar();\r\n    while(ch&lt;'0'||ch&gt;'9') ch=getchar();\r\n    while(ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-'0';ch=getchar();}\r\n    return x;\r\n}\r\nint dfn[N],low[N],tp,a,b,n,m,lj[N],to[M],fro[M],cnt,q[N],tq,ans;\r\nvoid add(int u,int v){cnt++;to[cnt]=v;fro[cnt]=lj[u];lj[u]=cnt;}\r\nbool vs[N];\r\nvoid tj(int k)\r\n{\r\n    dfn[k]=low[k]=++tp;\r\n    q[++tq]=k;\r\n    vs[k]=1;\r\n    for(int i=lj[k];i;i=fro[i])\r\n    {\r\n        if(!dfn[to[i]])\r\n        {\r\n            tj(to[i]);\r\n            low[k]=min(low[k],low[to[i]]);\r\n        }\r\n        else if(vs[to[i]]) low[k]=min(low[k],low[to[i]]);\r\n    }\r\n    if(dfn[k]==low[k])\r\n    {\r\n        int d=0;\r\n        while(q[tq]!=k)\r\n        {\r\n            vs[q[tq--]]=0;\r\n            d++;\r\n        }\r\n        vs[q[tq--]]=0;\r\n        d++;\r\n        if(d&gt;1) ans++;\r\n    }\r\n}\r\nint main()\r\n{\r\n    n=read(); m=read();\r\n    for(int i=0;i&lt;m;i++)\r\n    {\r\n        a=read();b=read();\r\n        add(a,b);\r\n    }\r\n    for(int i=1;i&lt;=n;i++) if(!vs[i]) tj(i);\r\n    printf(\"%d\\n\",ans);\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; 1654: [Usaco2006 Jan]The Cow Prom \u5976\u725b\u821e\u4f1a Time Limi [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[29],"class_list":["post-343","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-tarjan"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/343","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=343"}],"version-history":[{"count":2,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/343\/revisions"}],"predecessor-version":[{"id":347,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/343\/revisions\/347"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}