{"id":631,"date":"2013-09-15T14:43:45","date_gmt":"2013-09-15T06:43:45","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=631"},"modified":"2013-09-15T14:43:45","modified_gmt":"2013-09-15T06:43:45","slug":"%e4%b9%9d%e5%ba%a6oj-%e9%a2%98%e7%9b%ae1109%ef%bc%9a%e8%bf%9e%e9%80%9a%e5%9b%be","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=631","title":{"rendered":"\u4e5d\u5ea6OJ \u9898\u76ee1109\uff1a\u8fde\u901a\u56fe"},"content":{"rendered":"<dl>\n<dt><b>\u9898\u76ee\u63cf\u8ff0\uff1a<\/b><\/dt>\n<dd>\u00a0\u00a0\u00a0 \u7ed9\u5b9a\u4e00\u4e2a\u65e0\u5411\u56fe\u548c\u5176\u4e2d\u7684\u6240\u6709\u8fb9\uff0c\u5224\u65ad\u8fd9\u4e2a\u56fe\u662f\u5426\u6240\u6709\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\u3002\n<\/dd>\n<\/dl>\n<dl>\n<dt><b>\u8f93\u5165\uff1a<\/b><\/dt>\n<dd>\u00a0\u00a0\u00a0 \u6bcf\u7ec4\u6570\u636e\u7684\u7b2c\u4e00\u884c\u662f\u4e24\u4e2a\u6574\u6570 n \u548c m\uff080&lt;=n&lt;=1000\uff09\u3002n \u8868\u793a\u56fe\u7684\u9876\u70b9\u6570\u76ee\uff0cm \u8868\u793a\u56fe\u4e2d\u8fb9\u7684\u6570\u76ee\u3002\u5982\u679c n \u4e3a 0 \u8868\u793a\u8f93\u5165\u7ed3\u675f\u3002\u968f\u540e\u6709 m \u884c\u6570\u636e\uff0c\u6bcf\u884c\u6709\u4e24\u4e2a\u503c x \u548c y\uff080&lt;x, y &lt;=n\uff09\uff0c\u8868\u793a\u9876\u70b9 x \u548c y \u76f8\u8fde\uff0c\u9876\u70b9\u7684\u7f16\u53f7\u4ece 1 \u5f00\u59cb\u8ba1\u7b97\u3002\u8f93\u5165\u4e0d\u4fdd\u8bc1\u8fd9\u4e9b\u8fb9\u662f\u5426\u91cd\u590d\u3002\n<\/dd>\n<\/dl>\n<dl>\n<dt><b>\u8f93\u51fa\uff1a<\/b><\/dt>\n<dd>\u00a0\u00a0\u00a0 \u5bf9\u4e8e\u6bcf\u7ec4\u8f93\u5165\u6570\u636e\uff0c\u5982\u679c\u6240\u6709\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\uff0c\u8f93\u51fa&#8221;YES&#8221;\uff0c\u5426\u5219\u8f93\u51fa&#8221;NO&#8221;\u3002\n<\/dd>\n<\/dl>\n<dl>\n<dt><b>\u6837\u4f8b\u8f93\u5165\uff1a<\/b><\/dt>\n<dd>\n<pre>4 3\n1 2\n2 3\n3 2\n3 2\n1 2\n2 3\n0 0<\/pre>\n<\/dd>\n<\/dl>\n<dl>\n<dt><b>\u6837\u4f8b\u8f93\u51fa\uff1a<\/b><\/dt>\n<dd>\n<pre>NO\nYES<\/pre>\n<\/dd>\n<\/dl>\n<p>====================================<br \/>\n\u8fd9\u4e24\u5929\u5f04\u51e0\u9053\u7b80\u5355\u7684\u505a\u505a&#8230;<br \/>\n\u8fd9\u4e2a\u662f\u56fe\u8054\u901a\u7684\u68c0\u6d4b\uff0c\u53ef\u4ee5\u7528DFS\u6216\u8005BFS\u505a\uff0c\u5176\u5b9e\u51fd\u6570\u7ed9\u4e2aint\u8fd4\u56de\u503c\uff0c\u8fd4\u56de\u8fd9\u4e2a\u8282\u70b9\u6807\u8bb0\u4e86\u51e0\u4e2a\uff0c\u8fd9\u6837\u540e\u9762main\u51fd\u6570\u91cc\u9762\u5c31\u4e0d\u7528\u518d\u904d\u5386\u4e00\u6b21visited\u6570\u7ec4\u4e86~<br \/>\n\u53d1\u73b0\u4ee5\u524d\u7533\u8bf7\u7684\u7a7a\u95f4\u90fd\u4e0ddelete\u7684\uff0c\u73b0\u5728\u611f\u89c9\u5c31\u50cf\u4fbf\u4fbf\u4e86\u6ca1\u64e6\u5c41\u80a1\u4e00\u6837&#8230;<br \/>\n\u8c03\u8bd5\u51fa\u6765\u7b2c\u4e00\u904d\u53d1\u73b0\u600e\u4e48\u90fd\u4e0d\u5bf9\uff0c\u540e\u6765\u7ec6\u770b\u53d1\u73b0\u7533\u8bf7\u51fa\u6765\u7684\u4e8c\u7ef4\u6570\u7ec4\u6ca1\u6709\u521d\u59cb\u5316&#8230;\u5657<br \/>\n\u5450\uff0c\u5982\u679c\u662fBFS\u7684\u8bdd\uff0c\u6309\u7167\u6570\u636e\u7ed3\u6784\u4e66\u4e0a\u8bb2\uff0c\u7528\u961f\u5217\u6765\u641e\uff0c\u4e0d\u7528\u9012\u5f52\u5c31\u884c\u4e86\u3002\u628a\u672c\u5c42\u8bbf\u95ee\u5230\u7684\u8282\u70b9\u585e\u5230\u5de5\u4f5c\u961f\u5217\u4e2d\u5c31\u884c..<br \/>\n====================================<br \/>\n<code lang=\"c++\"><br \/>\n#include <iostream><br \/>\nusing namespace std;<br \/>\nvoid DFS( bool **connMatrix, bool *visited, int N, int c)<br \/>\n{<br \/>\n    \/\/connMatrix: \u8fde\u901a\u77e9\u9635<br \/>\n    \/\/visited \uff1a\u662f\u5426\u8bbf\u95ee<br \/>\n    \/\/N : \u8282\u70b9\u6570<br \/>\n    \/\/c : \u5f53\u524d\u8282\u70b9\u7f16\u53f7<br \/>\n    visited[c] = true; \/\/Mark current node as visited<br \/>\n    int i;<br \/>\n    for(i=0; i<n; i++)\n    {\n        if(connMatrix[c][i] == 0)\n            continue; \/\/c and i are not connected.\n        if(visited[i])\n            continue; \/\/Node i have been visited\n        DFS(connMatrix, visited, N, i); \/\/Try visit next node\n    }\n}\nint main()\n{\n    int N = 0;\n    int M;\n    while(cin >> N && N != 0)<br \/>\n    {<br \/>\n        cin >> M;<br \/>\n        \/\/Create matrix and visited<br \/>\n        bool **connMat = new bool*[N];<br \/>\n        bool *visited = new bool[N];<br \/>\n        int i;<br \/>\n        for(i=0; i<n; i++)\n        {\n            connMat[i] = new bool[N];\n            int j;\n            for(j=0; j<n; j++)\n                connMat[i][j] = false;\n            visited[i] = false;\n        }\n        \/\/Data input\n        for(i=0; i<m; i++)\n        {\n            int x, y;\n            cin >> x >> y;<br \/>\n            x--;<br \/>\n            y--;  \/\/Subscript starts from 1 in the input<br \/>\n            connMat[x][y] = true;<br \/>\n            connMat[y][x] = true;<br \/>\n        }<br \/>\n        \/\/Manipulate<br \/>\n        DFS(connMat, visited, N, 0);<br \/>\n        bool flag = true;<br \/>\n        for(i=0; i<n; i++)\n        {\n            if(visited[i] == false)\n            {\n                flag = false;\n                break;\n            }\n        }\n        if(flag)\n            cout << \"YES\" << endl;\n        else\n            cout << \"NO\" << endl;\n        \/\/Delete matrix and visited\n        for(i=0; i<n; i++)\n            delete []connMat[i];\n        delete []connMat;\n        delete []visited;\n    }\n    return 0;\n}\n\/**************************************************************\n    Problem: 1109\n    User: iorange\n    Language: C++\n    Result: Accepted\n    Time:80 ms\n    Memory:2444 kb\n****************************************************************\/\n<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0\uff1a \u00a0\u00a0\u00a0 \u7ed9\u5b9a\u4e00\u4e2a\u65e0\u5411\u56fe\u548c\u5176\u4e2d\u7684\u6240\u6709\u8fb9\uff0c\u5224\u65ad\u8fd9\u4e2a\u56fe\u662f\u5426\u6240\u6709\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\u3002 \u8f93\u5165\uff1a \u00a0\u00a0\u00a0 \u6bcf\u7ec4\u6570\u636e\u7684\u7b2c\u4e00\u884c\u662f\u4e24\u4e2a\u6574\u6570 n \u548c m\uff080&lt;=n&lt;=1000\uff09\u3002n \u8868\u793a\u56fe\u7684\u9876\u70b9\u6570\u76ee\uff0cm \u8868\u793a\u56fe\u4e2d\u8fb9\u7684\u6570\u76ee\u3002\u5982\u679c n \u4e3a 0 \u8868\u793a\u8f93\u5165\u7ed3\u675f\u3002\u968f\u540e\u6709 m \u884c\u6570\u636e\uff0c\u6bcf\u884c\u6709\u4e24\u4e2a\u503c x \u548c y\uff080&lt;x, y &lt;=n\uff09\uff0c\u8868\u793a\u9876\u70b9 x \u548c y \u76f8\u8fde\uff0c\u9876\u70b9\u7684\u7f16\u53f7\u4ece 1 \u5f00\u59cb\u8ba1\u7b97\u3002\u8f93\u5165\u4e0d\u4fdd\u8bc1\u8fd9\u4e9b\u8fb9\u662f\u5426\u91cd\u590d\u3002 \u8f93\u51fa\uff1a \u00a0\u00a0\u00a0 \u5bf9\u4e8e\u6bcf\u7ec4\u8f93\u5165\u6570\u636e\uff0c\u5982\u679c\u6240\u6709\u9876\u70b9\u90fd\u662f\u8fde\u901a\u7684\uff0c\u8f93\u51fa&#8221;YES&#8221;\uff0c\u5426\u5219\u8f93\u51fa&#8221;NO&#8221;\u3002 \u6837\u4f8b\u8f93\u5165\uff1a 4 3 1 2 2 3 3 2 3 2 1 2 2 3 0 0 \u6837\u4f8b\u8f93\u51fa\uff1a NO YES ==================================== \u8fd9\u4e24\u5929\u5f04\u51e0\u9053\u7b80\u5355\u7684\u505a\u505a&#8230; \u8fd9\u4e2a\u662f\u56fe\u8054\u901a\u7684\u68c0\u6d4b\uff0c\u53ef\u4ee5\u7528DFS\u6216\u8005BFS\u505a\uff0c\u5176\u5b9e\u51fd\u6570\u7ed9\u4e2aint\u8fd4\u56de\u503c\uff0c\u8fd4\u56de\u8fd9\u4e2a\u8282\u70b9\u6807\u8bb0\u4e86\u51e0\u4e2a\uff0c\u8fd9\u6837\u540e\u9762main\u51fd\u6570\u91cc\u9762\u5c31\u4e0d\u7528\u518d\u904d\u5386\u4e00\u6b21visited\u6570\u7ec4\u4e86~ \u53d1\u73b0\u4ee5\u524d\u7533\u8bf7\u7684\u7a7a\u95f4\u90fd\u4e0ddelete\u7684\uff0c\u73b0\u5728\u611f\u89c9\u5c31\u50cf\u4fbf\u4fbf\u4e86\u6ca1\u64e6\u5c41\u80a1\u4e00\u6837&#8230; [&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":[132],"class_list":["post-631","post","type-post","status-publish","format-standard","hentry","category-study","tag-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/631","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=631"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/631\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=631"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=631"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=631"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}