CodeForces 623A Graph and String

Posted on By 二价氢

题目大意

给定一个图,要求给每个顶点染色a, bc,要求连边的只能是染成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

但我么仍然可以利用这个充分条件,将补图中有边的点染成ac,将补图中没有边的点染成b,可以证明,如果染色方案存在,那么这一定是一种合法的染色方案,接着,把我们的染色结果代入原图验证即可,总的时间复杂度为

代码

#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;
}