{"id":793,"date":"2019-09-25T21:01:31","date_gmt":"2019-09-25T13:01:31","guid":{"rendered":"http:\/\/149.129.74.185\/?p=793"},"modified":"2019-09-25T21:01:31","modified_gmt":"2019-09-25T13:01:31","slug":"patadvanced1154-vertex-coloring-25-%e5%88%86","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=793","title":{"rendered":"PAT(Advanced)1154 Vertex Coloring (25 \u5206)"},"content":{"rendered":"

1154<\/span>\u00a0<\/span>Vertex Coloring<\/span>\u00a0<\/span>(25\u00a0<\/span>\u5206<\/span>)<\/span><\/h3>\n

A\u00a0<\/span>proper vertex coloring<\/strong>\u00a0<\/span>is a labeling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most\u00a0<\/span><\/span><\/span>k<\/span><\/span><\/span><\/span>\u00a0<\/span>colors is called a (proper)\u00a0<\/span><\/span><\/span>k<\/span><\/span><\/span><\/span>-coloring<\/strong>.<\/p>\n

Now you are supposed to tell if a given coloring is a proper\u00a0<\/span><\/span><\/span>k<\/span><\/span><\/span><\/span>-coloring.<\/p>\n

Input Specification:<\/h3>\n

Each input file contains one test case. For each case, the first line gives two positive integers\u00a0<\/span><\/span><\/span>N<\/span><\/span><\/span><\/span>\u00a0<\/span>and\u00a0<\/span><\/span><\/span>M<\/span><\/span><\/span><\/span>\u00a0<\/span>(both no more than\u00a0<\/span><\/span><\/span>1<\/span>0<\/span>\u200b<\/span>4<\/span><\/span><\/span>\u200b<\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span>), being the total numbers of vertices and edges, respectively. Then\u00a0<\/span><\/span><\/span>M<\/span><\/span><\/span><\/span>\u00a0<\/span>lines follow, each describes an edge by giving the indices (from 0 to\u00a0<\/span><\/span><\/span>N<\/span>\u2212<\/span>1<\/span><\/span><\/span><\/span>) of the two ends of the edge.<\/p>\n

After the graph, a positive integer\u00a0<\/span><\/span><\/span>K<\/span><\/span><\/span><\/span>\u00a0<\/span>(<\/span><\/span>\u2264<\/span><\/span><\/span><\/span>\u00a0<\/span>100) is given, which is the number of colorings you are supposed to check. Then\u00a0<\/span><\/span><\/span>K<\/span><\/span><\/span><\/span>\u00a0<\/span>lines follow, each contains\u00a0<\/span><\/span><\/span>N<\/span><\/span><\/span><\/span>\u00a0<\/span>colors which are represented by non-negative integers in the range of\u00a0<\/span>int<\/strong>. The\u00a0<\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>-th color is the color of the\u00a0<\/span><\/span><\/span>i<\/span><\/span><\/span><\/span>-th vertex.<\/p>\n

Output Specification:<\/h3>\n

For each coloring, print in a line\u00a0<\/span>k-coloring<\/code>\u00a0<\/span>if it is a proper\u00a0<\/span>k<\/code>-coloring for some positive\u00a0<\/span>k<\/code>, or\u00a0<\/span>No<\/code>\u00a0<\/span>if not.<\/p>\n

Sample Input:<\/h3>\n
10 11\r\n8 7\r\n6 8\r\n4 5\r\n8 4\r\n8 1\r\n1 2\r\n1 4\r\n9 8\r\n9 1\r\n1 0\r\n2 4\r\n4\r\n0 1 0 1 4 1 0 1 3 0\r\n0 1 0 1 4 1 0 1 0 0\r\n8 1 0 1 4 1 0 5 3 0\r\n1 2 3 4 5 6 7 8 8 9\r\n<\/code><\/pre>\n
Sample Output:<\/h3>\n
4-coloring\r\nNo\r\n6-coloring\r\nNo<\/code><\/pre>\n
\u9898\u76ee\u89e3\u8bfb\uff1a\u9876\u70b9\u7740\u8272\u9898\uff0c\u89c4\u5b9a\u5728\u540c\u4e00\u6761\u8fb9\u4e0a\u7684\u4e24\u4e2a\u9876\u70b9\u4e0d\u53ef\u4ee5\u7740\u540c\u4e00\u989c\u8272\uff0c\u5148\u8f93\u5165\u9876\u70b9\u6570\u3001\u8fb9\u6570\uff0c\u8f93\u5165\u8fb9\u7684\u9876\u70b9\uff0c\u63a5\u7740\u8f93\u5165k\u6b21\u6d4b\u8bd5\u6761\u4ef6\uff0c\u6bcf\u4e00\u884c\u8868\u793a\u6bcf\u6b21\u6d4b\u8bd5\u6bcf\u4e2a\u9876\u70b9\u7684\u7740\u8272\u60c5\u51b5\u3002\u5982\u679c\u6ee1\u8db3\u6761\u4ef6\u5219\u8f93\u51fa\u662f\u51e0\u8272\u7740\u8272\u56fe\u5f62\uff0c\u82e5\u4e0d\u6ee1\u8db3\u5219\u8f93\u51fa\u201cNo\u201d<\/p>\n
\u89e3\u9898\u601d\u8def\uff1a \u6bd4\u8f83\u7b80\u5355\u7684\u904d\u5386\u56fe\u7684\u9898\uff0c\u7528\u8fb9\u6765\u5b58\u50a8\u56fe\uff0c\u53e6\u5f00\u4e00\u4e2a\u989c\u8272\u7684\u6570\u7ec4\u6765\u8bb0\u5f55\u989c\u8272\u7684\u60c5\u51b5\uff0c\u7528set\u6765\u6570\u6709\u591a\u5c11\u4e2a\u989c\u8272\u4f1a\u6bd4\u8f83\u65b9\u4fbf\uff0c\u6ca1\u4ec0\u4e48\u5751\u7684\u597d\u9898QWQ\uff01\uff01<\/p>\n
<\/p>\n
AC\u4ee3\u7801<\/p>\n
#include <iostream>\r\n#include <vector>\r\n#include <memory>\r\n#include <set>\r\nusing namespace std;\r\nstruct edge {\r\n\tint v;\r\n\tint u;\r\n\tedge(int _v, int _u) {\r\n\t\tv = _v;\r\n\t\tu = _u;\r\n\t}\r\n};\r\nvector<edge> graph;\r\nint color[10004];\r\nint n, m;\r\nset<int> colorset;\r\nint main()\r\n{\r\n\tscanf(\"%d %d\", &n, &m);\r\n\tfor (int i = 0; i < m; i++) {\r\n\t\tint a, b;\r\n\t\tscanf(\"%d %d\", &a, &b);\r\n\t\tgraph.push_back(edge(a,b));\r\n\t}\r\n\tint k;\r\n\tscanf(\"%d\", &k);\r\n\tfor (int i = 0; i < k; i++) {\r\n\t\tint flag = 1;\r\n\t\tcolorset.clear();\r\n\t\tfill(color, color + 10004, -1);\r\n\t\tfor (int i = 0; i < n; i++) {\r\n\t\t\tscanf(\"%d\", &color[i]);\r\n\t\t\tcolorset.insert(color[i]);\r\n\t\t}\r\n\t\tfor (auto edg : graph) {\r\n\t\t\tif (color[edg.u] == color[edg.v]) {\r\n\t\t\t\tflag = 0;\r\n\t\t\t}\r\n\t\t}\r\n\t\tif (flag)\r\n\t\t\tprintf(\"%d-coloring\\n\", colorset.size());\r\n\t\telse {\r\n\t\t\tprintf(\"No\\n\");\r\n\t\t}\r\n\t}\r\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1154\u00a0Vertex Coloring\u00a0(25\u00a0\u5206) A\u00a0proper vertex colori […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,18,17],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/793"}],"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=793"}],"version-history":[{"count":1,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/793\/revisions"}],"predecessor-version":[{"id":794,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/793\/revisions\/794"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=793"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=793"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=793"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}