{"id":668,"date":"2019-09-01T19:59:44","date_gmt":"2019-09-01T11:59:44","guid":{"rendered":"http:\/\/149.129.74.185\/?p=668"},"modified":"2019-09-02T12:09:57","modified_gmt":"2019-09-02T04:09:57","slug":"%e5%ad%a6%e5%88%b0%e4%ba%86-2019-9-1","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=668","title":{"rendered":"PAT\u5b66\u5230\u4e86 2019\/9\/1"},"content":{"rendered":"

\u3010\u672c\u8d28\u662f\u770b\u522b\u4eba\u7684\u4ee3\u7801\u5b66\u4e1c\u897f\u3011<\/span><\/p>\n

1<\/span>.\u90bb\u63a5\u77e9\u9635\u8bbf\u95ee\u56fe\u6240\u9700\u6570\u636e\u7ed3\u6784<\/span><\/p>\n

int edge[][];<\/code><\/span><\/p>\n

int visited[];<\/code><\/span><\/p>\n

\u00a0\u5176\u4e2d visited \u9700\u8981\u521d\u59cb\u5316\u5168\u90e8\u4e3a0\uff0c\u4e00\u79cd\u76f8\u5bf9\u7b80\u5355\u7684\u65b9\u5f0f\u662f\u4f7f\u7528 #include<memory.h>\/<string.h> \u7684 memset\u51fd\u6570\uff1a<\/span><\/p>\n

memset(visited,0,sizeof(visited));<\/code><\/span><\/p>\n

2.\u90bb\u63a5\u77e9\u9635\u8bbf\u95ee\u56fe\u7684\u4e24\u79cd\u57fa\u672c\u65b9\u6cd5<\/span><\/p>\n

DFS:<\/span><\/p>\n

void dfs( int v ) {\r\n\tvisited[v] = 1;\r\n\tfor (int i = 1; i <= N; i++) {\r\n\t\tif (!visited[i] && edge[i][v] == 1)\r\n\t\t\tdfs(i);\r\n\t}\r\n}<\/code><\/pre>\n
BFS:<\/p>\n
void bfs(int v) {\r\n\tqueue<int> q;\r\n\tq.push(v);\r\n\tvisited[v] = 1;\r\n\twhile (!q.empty()) {\r\n\t\tint n = q.front();\r\n\t\tq.pop();\r\n\t\tfor (int i = 1; i <= N; i++) {\r\n\t\t\tif (!visited[i] && edge[n][i] == 1) {\r\n\t\t\t\tq.push(i);\r\n\t\t\t\tvisited[i] = true;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}<\/code><\/pre>\n
3.cin\u548ccout\u7684\u6027\u80fd\u5f88\u5dee\uff0c\u6458\uff1a<\/span><\/p>\n
cout\u548ccin\u7684\u8bbe\u8ba1\uff0c\u53ef\u80fd\u6bd4\u6211\u4eec\u60f3\u8c61\u7684\u590d\u6742\u7684\u591a\uff0c\u4ece\u5b9e\u9645\u6d4b\u8bd5\u7684\u7ed3\u679c\uff0c\u901f\u5ea6\u6bd4printf\u548cscanf\u6162\u4e00\u4e2a\u6570\u91cf\u7ea7\u4ee5\u4e0a\u3002\u5f71\u54cdcout\u548ccin\u7684\u6027\u80fd\u7684\u6709\u4e24\u4e2a\u65b9\u9762\uff1a\u540c\u6b65\u6027\u548c\u7f13\u51b2\u533a\uff0c\u540c\u6b65\u6027\u53ef\u4ee5\u901a\u8fc7ios_base::sync_with_stdio(false)\u7981\u7528\uff1b\u64cd\u4f5c\u7cfb\u7edf\u4f1a\u5bf9\u7f13\u51b2\u533a\u8fdb\u884c\u7ba1\u7406\u548c\u4f18\u5316\uff0c\u4f46\u5341\u5206\u6709\u9650\uff0c\u4f7f\u7528\u4e86endl\u4e4b\u540e\uff0c\u4f1a\u5bf9\u7f13\u51b2\u533a\u6267\u884c\u6e05\u7a7a\u64cd\u4f5c\uff0c\u8fd9\u4e2a\u8fc7\u7a0b\u4f1a\u5148\u6267\u884c\u2019\\n\u2019\uff0c\u518d\u6267\u884cflush\u64cd\u4f5c\uff0c\u975e\u5e38\u6f2b\u957f\uff0c\u6240\u4ee5\u5c3d\u91cf\u4f7f\u7528\u2018\\n\u2019\u800c\u4e0d\u662fendl\u6267\u884c\u6362\u884c\u3002\u7136\u540e\uff0c\u8fd8\u6709\u4e00\u4e2acout\u548ccin\u7684\u7ed1\u5b9a\u6548\u679c\uff0c\u4e24\u8005\u540c\u65f6\u4f7f\u7528\u7684\u8bdd\uff0ccin\u4e0ecout\u4ea4\u66ff\u64cd\u4f5c\uff0c\u4f1a\u6709\u4e00\u4e2aflush\u8fc7\u7a0b\uff0c\u6240\u4ee5\u8fd8\u662f\u4f1a\u5f88\u6f2b\u957f\uff0c\u53ef\u4ee5\u901a\u8fc7cin.tie(0)\u7981\u7528\u7ed1\u5b9a\u3002 <\/span>
\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/span>
\n\u7248\u6743\u58f0\u660e\uff1a\u672c\u6587\u4e3aCSDN\u535a\u4e3b\u300cCodeLike\u300d\u7684\u539f\u521b\u6587\u7ae0\uff0c\u9075\u5faa CC 4.0 BY-SA \u7248\u6743\u534f\u8bae\uff0c\u8f6c\u8f7d\u8bf7\u9644\u4e0a\u539f\u6587\u51fa\u5904\u94fe\u63a5\u53ca\u672c\u58f0\u660e\u3002<\/span>
\n\u539f\u6587\u94fe\u63a5\uff1ahttps:\/\/blog.csdn.net\/cv_jason\/article\/details\/81019874<\/span><\/p>\n
\u00a04.\u5e76\u67e5\u96c6\u4e24\u4e2a\u6838\u5fc3\u7b97\u6cd5<\/span><\/p>\n
Find\uff08\u67e5\u627e\u6839\u8282\u70b9\uff09<\/span><\/p>\n
int father[];\r\n\r\nfor( int i = 0 ; i < father.size() ; i ++ ){\r\n\tfather[i] = i;\r\n}\r\n\r\nint findFather(int child) {\r\n\tif (child == father[child])\r\n\t\treturn child;\r\n\treturn father[child] = findFather(father[child]);\r\n}<\/code><\/pre>\n
\u00a0<\/span><\/p>\n
union\/merge\uff08\u538b\u7f29\u8def\u5f84\uff09<\/span><\/p>\n
 <\/p>\n
void merge(int u, int v) {\r\n\tint fu = find(u);\r\n\tint fv = find(v);\r\n\tif (fu != fv) {\r\n\t\tfather[fu] = fv;\r\n\t}\r\n}<\/code><\/pre>\n
5.\u79d1\u5b66\u8ba1\u6570\u6cd5: 1e5 = 1*105<\/sup><\/span><\/p>\n
6.\u6ce8\u610f\u53cc\u7b49\u53f7\uff01\uff01<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
\u3010\u672c\u8d28\u662f\u770b\u522b\u4eba\u7684\u4ee3\u7801\u5b66\u4e1c\u897f\u3011 1.\u90bb\u63a5\u77e9\u9635\u8bbf\u95ee\u56fe\u6240\u9700\u6570\u636e\u7ed3\u6784 int edge[][]; int v […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,17],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/668"}],"collection":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=668"}],"version-history":[{"count":4,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/668\/revisions"}],"predecessor-version":[{"id":677,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/668\/revisions\/677"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=668"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}