一堆 Cornner Case 的大分讨,我们全队一边写一边补情况,WA 了五发终于干过去了
首先当图中存在某个环时,我们只要给环上的所有点赋值为 \(1\) 即可;又因为图连通所以只要考虑树的情况即可
考虑如果存在一个度数 \(\ge 4\) 的点,将其赋值为 \(2\) 并将其周围的四个点赋值为 \(1\) 即可
如果存在两个及以上度数为三的点,只要将其中两个的路径上所有点赋值为 \(2\),并在端点处各选两个点赋值为 \(1\) 即可
难点在于有且仅有一个度数为三的点的情况,因为我们很容易证明一条链的情况是无解的
考虑此时的图一定形如一个中心点,往外延申出三条链,不妨将这三条链的长度记为 \(a,b,c(a\le b\le c)\)
考虑找出一些最小的有解结构,方法可以是人类智慧也可以是爆搜,最后发现以下三种 Case 是合法的:
然后这题就做完了,判断一个图是否满足上述条件即可,代码是徐神写的
#include <bits/stdc++.h>
std::vector<int> work() {
int n, m; std::cin >> n >> m;
std::vector<std::vector<int>> out(n, std::vector<int>());
for(int i = 0, f, t; i < m; ++i) {
std::cin >> f >> t;
f--; t--;
out[f].push_back(t);
out[t].push_back(f);
}
std::vector<int> ans(n, 0);
std::vector<bool> vis(n, false);
std::function<bool(int, int)> dfs = [&](int cur, int fa) -> bool {
vis[cur] = true;
for(auto out: out[cur]) {
if(out == fa) continue;
if(vis[out] || dfs(out, cur))
return ans[cur] = 1, vis[cur] = true;
}
return false;
};
for(int i = 0; i < n; ++i) if(!vis[i] && dfs(i, -1)) return ans;
for(int i = 0; i < n; ++i) if(out[i].size() >= 4) {
ans[i] = 2;
for(int j = 0; j < 4; ++j) ans[out[i][j]] = 1;
return ans;
}
auto ahaha = [&](auto self, int cur, int fa) -> int {
for(auto out: out[cur]) if(out != fa) return self(self, out, cur) + 1;
return 1;
};
auto fill = [&](auto self, int cur, int fa, std::vector<int> val) -> void {
if(val.empty()) return ;
ans[cur] = val.back(); val.pop_back();
for(auto out: out[cur]) if(out != fa) self(self, out, cur, val);
};
vis.assign(n, false);
auto dfs2 = [&](auto self, int cur, int fa) -> int {
vis[cur] = true;
if(out[cur].size() == 3) return ans[cur] = 2, cur;
for(auto out: out[cur]) if(out != fa) {
int res = self(self, out, cur);
if(res >= 0) return ans[cur] = 2, res;
}
return -1;
};
bool flag = false;
for(int i = 0; i < n && !flag; ++i) if(!vis[i] && out[i].size() == 3) {
vis[i] = true;
for(auto out: out[i]) {
if(flag) break;
int res = dfs2(dfs2, out, i);
// std::cerr << "res = " << res << char(10);
if(res >= 0) {
ans[i] = 2;
flag = true;
}
}
}
if(flag) {
for(int i = 0; i < n; ++i) if(ans[i] == 2) for(auto out: out[i]) if(ans[out] == 0) ans[out] = 1;
return ans;
}
for(int i = 0; i < n; ++i) if(out[i].size() == 3) {
std::pair<int, int> len[3];
for(int j = 0; j < 3; ++j) len[j] = {ahaha(ahaha, out[i][j], i), out[i][j]};
std::sort(len, len + 3);
// std::cerr << "len[] = [";
// for(int j = 0; j < 3; ++j) std::cerr << len[j].first << (j == 2 ? "]\n" : ", ");
if(len[0].first >= 2 && len[1].first >= 2 && len[2].first >= 2) {
ans[i] = 3;
fill(fill, len[0].second, i, std::vector<int>{1, 2});
fill(fill, len[1].second, i, std::vector<int>{1, 2});
fill(fill, len[2].second, i, std::vector<int>{1, 2});
return ans;
}
if(len[0].first >= 1 && len[1].first >= 2 && len[2].first >= 5) {
ans[i] = 6;
fill(fill, len[0].second, i, std::vector<int>{3});
fill(fill, len[1].second, i, std::vector<int>{2, 4});
fill(fill, len[2].second, i, std::vector<int>{1, 2, 3, 4, 5});
return ans;
}
if(len[0].first >= 1 && len[1].first >= 3 && len[2].first >= 3) {
ans[i] = 4;
fill(fill, len[0].second, i, std::vector<int>{2});
fill(fill, len[1].second, i, std::vector<int>{1, 2, 3});
fill(fill, len[2].second, i, std::vector<int>{1, 2, 3});
return ans;
}
}
return {};
}
int main() {
std::ios::sync_with_stdio(false);
int t; std::cin >> t; while(t--) {
auto ans = work();
if(ans.empty()) std::cout << "NO\n";
else {
std::cout << "YES\n";
int n = ans.size();
for(int i = 0; i < n; ++i) std::cout << ans[i] << char(i == n - 1 ? 10 : 32);
}
}
return 0;
}
标签:std,Machine,cur,int,Perpetual,len,Motion,ans,out
From: https://www.cnblogs.com/cjjsb/p/18359544