【小码匠自习室】并查集板子题：ABC288 - C - Don’t be cycle，亮点在参考题解
补题
周六的时候和小姨去吃饭了，晚上没能来的及线上赛，周日继续补题。
题目不难，难在我把并查集的板子打错了，稍微调试了几分钟。
本题的亮点：请移步参考题解, 后面我抽时间在研究
题目
- https://atcoder.jp/contests/abc288/tasks/abc288_c
N顶点M边的简单无向图。顶点编号为1到N，第i边为顶点A
和顶点B
连接。从该图表中删除0条以上的几条边，使图表不具有闭路时，请求出删除边的根数的最小值。
制約
- 给定的图表很单纯图
- 所有输入都是整数
入力
- N M
- A
B
- A
B
- A
B
出力
输出答案。
入力例 1
代码语言：javascript复制6 7
1 2
1 3
2 3
4 2
6 5
4 6
4 5
出力例 1
代码语言：javascript复制2
可以通过删除连接顶点1和顶点2的两条边、顶点4和连接顶点5的两条边等方法使图表不具有闭路。
1条以下边的删除不能使图表没有闭路，所以输出2。
入力例 2
代码语言：javascript复制4 2
1 2
3 4
出力例 2
代码语言：javascript复制0
入力例 3
代码语言：javascript复制5 3
1 2
1 3
2 3
出力例 3
代码语言：javascript复制1
小码匠
思路
- 采用并查集即可
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct edge {
int from;
int to;
};
struct UF {
vector<int> fa;
UF (int n) :
fa(n) {}
void initialize (int n) {
for (int i = 0; i < n; i) {
fa[i] = i;
}
}
int find(int a) {
if (a != fa[a]) {
fa[a] = find(fa[a]);
}
return fa[a];
}
void unite(int x, int y) {
int a = find(x);
int b = find(y);
if (a != b) {
fa[b] = a;
}
}
bool is_same(int x, int y) {
return find(x) == find(y);
}
};
void best_coder() {
int n, m;
cin >> n >> m;
queue<edge> g;
UF uf(n);
uf.initialize(n);
for (int i = 0; i < m; i) {
int a, b;
cin >> a >> b;
--a;
--b;
g.push({a, b});
}
int ans = 0;
while (!g.empty()) {
int a = g.front().from;
int b = g.front().to;
g.pop();
if (uf.is_same(a, b)) {
ans;
continue;
}
uf.unite(a, b);
}
cout << ans;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
参考题解
代码语言：javascript复制#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>
using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i) )
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i) )
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T>, greater<T>
template<typename T>
inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
const int INF = 1e9;
const int MOD = INF 7;
const LL LLINF = 1e18;
// UnionFind,素集合データ構造,DisjointSet
template<typename weight_type = int>
class union_find {
static_assert(
std::is_arithmetic<weight_type>::value,
"Invalid weight type");
private:
const std::function<void(int, int)> noop = [](int aa, int bb) {};
std::vector<int> uni;
std::vector<int> edge_count_;
std::vector<weight_type> weights;
int size_;
const void check(const int n) const {
if (this->group_size() < 0) {
assert(false);
}
if (!(0 <= n && n < this->all_size())) {
assert(false);
}
}
public:
union_find() : uni(0), edge_count_(0), weights(0), size_(-1) {}
union_find(const int n)
: uni(n, -1), edge_count_(n), weights(n), size_(n) {
this->check(n - 1);
}
union_find(const std::vector<weight_type> &_weights)
: uni(_weights.size(), -1), edge_count_(_weights.size()),
weights(_weights), size_(_weights.size()) {
this->check((int) _weights.size() - 1);
}
bool same(const int a, const int b) {
this->check(a);
this->check(b);
return this->find(a) == this->find(b);
}
int find(const int a) {
this->check(a);
return this->uni[a] < 0 ?
a :
this->uni[a] = this->find(this->uni[a]);
}
bool unite(int a, int b) {
return unite(a, b, noop);
}
bool unite(int a, int b, const std::function<void(int, int)> &f) {
a = this->find(a);
b = this->find(b);
this->edge_count_[a] ;
if (a == b) {
return false;
}
this->size_--;
if (this->uni[a] > this->uni[b]) {
std::swap(a, b);
}
f(a, b);
this->uni[a] = this->uni[b];
this->weights[a] = this->weights[b];
this->edge_count_[a] = this->edge_count_[b];
this->uni[b] = a;
return true;
}
const int group_size() const {
return this->size_;
}
const int all_size() const {
return this->uni.size();
}
const int size(const int a) {
this->check(a);
return -this->uni[this->find(a)];
}
const int edge_count(const int a) {
this->check(a);
return this->edge_count_[this->find(a)];
}
const weight_type weight(const int a) {
this->check(a);
return this->weights[this->find(a)];
}
};
void solve() {
int N, M;
cin >> N >> M;
union_find<> uf(N);
for (int i = 0; i < M; i) {
int a, b;
cin >> a >> b;
uf.unite(a - 1, b - 1);
}
int ok_cnt = 0;
set<int> checked;
for (int i = 0; i < N; i) {
const auto par = uf.find(i);
if (checked.count(par)) continue;
checked.emplace(par);
ok_cnt = uf.size(par) - 1;
}
cout << max(M - ok_cnt, 0) << "n";
}
int main(void) {
#ifndef ONLINE_JUDGE
const auto in_stream = freopen("../in.txt", "r", stdin);
if (in_stream == nullptr) {
cerr << "ERROR!" << endl;
return 1;
}
#endif
solve();
#ifndef ONLINE_JUDGE
fclose(in_stream);
#endif
}
