{"id":458,"date":"2018-12-05T20:46:48","date_gmt":"2018-12-05T12:46:48","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=458"},"modified":"2018-12-05T20:46:48","modified_gmt":"2018-12-05T12:46:48","slug":"lp2661-noip2015-%e4%bf%a1%e6%81%af%e4%bc%a0%e9%80%92","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/05\/lp2661-noip2015-%e4%bf%a1%e6%81%af%e4%bc%a0%e9%80%92\/","title":{"rendered":"lp2661 NOIP2015 \u4fe1\u606f\u4f20\u9012"},"content":{"rendered":"<p>\u627e\u56fe\u4e0a\u6700\u5c0f\u73af\u3002\u5220\u6389\u6240\u6709\u975e\u73af\u8fb9\u5373\u53ef\u3002<\/p>\n<pre class=\"pure-highlightjs\"><code class=\"cpp\">#include&lt;iostream&gt;\r\n#include&lt;cstdio&gt; \r\nstruct ee{\r\n    int v;\r\n    int nxt;\r\n}e[200005];\r\nint h[200005],et=0;\r\nbool vis[200005];\r\nint n,in[200005],a[200005];\r\ninline void add(int u,int v){\r\n    e[++et]=(ee){v,h[u]};\r\n    h[u]=et;\r\n}\r\ninline int fnd(int s){\r\n    int x=s,nxt=a[x],rt=1;\r\n    vis[x]=1;\r\n    while(!vis[nxt]){\r\n        ++rt;\r\n        x=nxt;\r\n        nxt=a[nxt];\r\n        vis[x]=1;\r\n    }\r\n    return rt;\r\n}\r\nvoid init(){\r\n    scanf(\"%d\",&amp;n);\r\n    int x;\r\n    for(int i=1;i&lt;=n;++i){\r\n        scanf(\"%d\",&amp;x);\r\n        add(i,x);\r\n        ++in[x];\r\n        a[i]=x;\r\n    }\r\n    int nw,nwxt;\r\n    for(int i=1;i&lt;=n;++i){\r\n        nw=i;\r\n        while(!in[nw]){\r\n            --in[a[nw]];\r\n            nwxt=nw;\r\n            nw=a[nw];\r\n            a[nwxt]=0;\r\n        }\r\n    }\r\n    int ans=0x3f3f3f3f;\r\n    for(int i=1;i&lt;=n;++i){\r\n        if(!vis[i]&amp;&amp;a[i]){\r\n            ans=std::min(ans,fnd(i));\r\n        }\r\n    }\r\n    printf(\"%d\\n\",ans);\r\n}\r\n\r\nint main(){\r\n    init();\r\n    return 0;\r\n}<\/code><\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u627e\u56fe\u4e0a\u6700\u5c0f\u73af\u3002\u5220\u6389\u6240\u6709\u975e\u73af\u8fb9\u5373\u53ef\u3002 #include&lt;iostream&gt; #include&lt; &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/05\/lp2661-noip2015-%e4%bf%a1%e6%81%af%e4%bc%a0%e9%80%92\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp2661 NOIP2015 \u4fe1\u606f\u4f20\u9012\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":[10,30,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/458"}],"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=458"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/458\/revisions"}],"predecessor-version":[{"id":459,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/458\/revisions\/459"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=458"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=458"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=458"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}