AtCoder Beginner Contest 327D
D - Good Tuple Problem (atcoder.jp)(种类并查集,二分图染色)
附上典题:P1892 [BOI2003] 团伙
种类并查集做法
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
template<typename T>
struct UFS {
T sz;
vector<T> rank, p;
void link(T x, T y) {
if (x == y)
return;
if (rank[x] > rank[y])
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
void init(int n) {
sz = n;
rank.resize(n + 1);
p.resize(n + 1);
for (int i = 0; i <= sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
T find(T x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
void unin(T x, T y) {
link(find(x), find(y));
}
void compress() {
for (int i = 0; i < sz; i++)
find(i);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, M;
cin >> n >> M;
vector<int> A(M), B(M);
for (auto &i : A)
cin >> i;
for (auto &i : B)
cin >> i;
UFS<i64> ufs;
ufs.init(n * 2);
for (int i = 0; i < M; i ++) {
int u = ufs.find(A[i]);
int v = ufs.find(B[i]);
if (u == v) {
cout << "No\n";
return 0;
}
ufs.unin(B[i] + n, u);
ufs.unin(A[i] + n, v);
}
cout << "Yes\n";
return 0;
}
二分图染色
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector G(n + 1, vector<int>());
vector<int> co(n + 1, -1), A(m), B(m);
for (auto &i : A) cin >> i;
for (auto &i : B) cin >> i;
for (int i = 0; i < m; i ++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
auto dfs = [&](auto self, int x, int val) -> void{
co[x] = val;
for (auto i : G[x]) {
if (co[i] == -1) {
self(self, i, val ^ 1);
} else if (co[i] == val) {
cout << "No\n";
exit(0);
}
}
};
for (int i = 1; i <= n; i ++)
if (co[i] == -1)
dfs(dfs, i, 0);
cout << "Yes\n";
return 0;
}
- Beginner AtCoder Contest 327beginner atcoder contest 327 327 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332