题目大意
给定一个图，要求给每个顶点染色a, b或c，要求连边的只能是染成aa,ab,bb,bc,cc的两点，问染色方案是否存在。
做法
如果考虑直接DFS染色，可能情况比较复杂，这时我们可以发现，如果考虑不连边的情况，那么两点只能是ac，所以可以求原图的补图进行DFS，再进行染ac的搜索
然而值得注意的一点是，如果染色时出现冲突，那么原图一定不存在染色方案，但如果染色时没有冲突，不代表一定存在染色方案，比如第23组数据：
7 13
1 2
1 3
1 7
2 3
2 5
2 7
3 7
4 5
4 6
4 7
5 6
5 7
6 7
但我么仍然可以利用这个充分条件，将补图中有边的点染成a或c，将补图中没有边的点染成b，可以证明，如果染色方案存在，那么这一定是一种合法的染色方案，接着，把我们的染色结果代入原图验证即可，总的时间复杂度为\(O(n^2)\)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
bool g[maxn][maxn];
vector<int> e[maxn];
char s[maxn];
int n, m;
bool dfs(int nd, char c) {
if (s[nd]) return s[nd] == c;
s[nd] = c;
for (int nx : e[nd]) {
bool tmp = dfs(nx, c == 'a' ? 'c' : 'a');
if (tmp == false) return false;
}
return true;
}
int abs(int x) {
return x > 0 ? x : -x;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j || g[i][j]) continue;
e[i].push_back(j);
}
bool tm = true;
for (int i = 1; i <= n; i++)
if (e[i].size() && !s[i])
tm = tm && dfs(i, 'a');
for (int i = 1; i <= n; i++)
if (e[i].size() == 0)
s[i] = 'b';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] && abs(s[i] - s[j]) > 1)
tm = false;
if (tm) {cout << "Yes\n" << &s[1] << endl;}
else {cout << "No\n";}
return 0;
}