1648 顶点着色 PAT1154
作者:
NikoNairre
,
2023-12-01 15:54:38
,
所有人可见
,
阅读 83
#include <iostream>
#include <set>
#include <string.h>
using namespace std;
const int N = 10010;
int h[N], e[N * 2], ne[N * 2], idx; //adjaceney list
int color[N];
int n, m, k;
void add_edge(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++ ;
}
bool check()
{
for (int u = 0; u < n; u++ ) {
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (color[u] == color[v]) return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof (h));
while (m-- ) {
//cout << "m: " << m << endl;
int a, b; cin >> a >> b;
add_edge(a, b), add_edge(b, a);
}
cin >> k;
while (k-- ) {
memset(color, -1, sizeof(color)); //refresh to a new round;
set<int> num_color;
for (int i = 0; i < n; i++ ) {
cin >> color[i];
num_color.emplace(color[i]);
}
int ck = num_color.size();
bool res = check();
if (res) {
cout << ck << "-coloring";
}
else {
cout << "No";
}
if (k) cout << endl;
}
return 0;
}