L2-023. 图着色问题*

时间:2022-07-05 04:01:52

L2-023. 图着色问题

参考博客

 #include <iostream>
#include <cstring>
#include <set> using namespace std; int v, e, k;
int map[][] = {};
int color[] = {}; bool flag = true;
bool vis[]; void isYes(int i) {
if (vis[i] || flag == false) {
return;
}
vis[i] = true;
for (int j = ; j < v; j++) {
if (color[i] == color[j] && map[i][j] == ) {
flag = false;
return;
} else if (map[i][j] == && vis[j] == false){
isYes(j);
}
}
} int main()
{
cin >> v >> e >> k;
for (int i = ; i < e; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
map[x][y] = ;
map[y][x] = ;
}
int m;
cin >> m;
for (int i = ; i < m; i++) {
set<int> s;
for (int j = ; j < v; j++) {
int c;
cin >> c;
s.insert(c);
color[j] = c;
}
if (s.size() != k) {
flag = false;
} else {
memset(vis, false, sizeof(vis));
flag = true;
for (int j = ; j < v; j++) {
isYes(j);
if (flag == false) {
break;
}
}
}
if (flag) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return ;
}