转化题意
把所有数连边,判断是否为二分图。
染色法
void solve() {
#define tests
int n;
std::cin >> n;
std::map<int, std::vector<int>> edge;
std::vector<bool> used(n + 1);
bool ok(true);
for (int i = 0; i < n; i++) {
int a, b;
std::cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
if (a == b or sz(edge[a]) > 2 or sz(edge[b]) > 2) {ok = false;}//出现次数大于二
}
if (not ok) {NO; return ;}
auto dfs = [&](auto self, int now) -> int {
used[now] = true;
for (auto to : edge[now]) if (not used[to]) {
return self(self, to) + 1;
}
return 1;
};//其实也是判断有没有奇环,显然总数加起来如果是奇数就是奇环
for (int i = 0; i < n; i++) {
if (not used[i + 1] and (dfs(dfs, i + 1) & 1)) {
ok = false;
}
}
ok ? YES : NO;
}
扩展域并查集
//扩展域并查集维护是否为二分图
//构造出x的敌人x+n和y的敌人y+n
//因为是分成两个集合,所以只要构造一个敌人(即另一个与自己相等的数,但不能放到同一个集合内所以称为敌人)
//把x和y的敌人合并,y和x的敌人合并
//如果x和自己的敌人在一个并查集,就不合法
void solve() {
#define tests
int n;
std::cin >> n;
std::vector<int> cnt(n);
DSU dsu(n * 2);
for (int i = 0; i < n; i++) {
int x, y;
std::cin >> x >> y;
x--, y--;
cnt[x]++; cnt[y]++;
dsu.merge(x, y + n); dsu.merge(x + n, y);
}
bool ok(true);
for (int i = 0; i < n; i++) {
if (cnt[i] > 2) ok = false;
if (dsu.find(i) == dsu.find(i + n)) ok = false;
}
ok ? YES : NO;
}
标签:二分,std,判断,ok,int,CF1702E,dsu,++,edge
From: https://www.cnblogs.com/kdlyh/p/18069306