526互联

AtCoder Beginner Contest 288 - C Don't be cycle 删除图中最少的边使得图中无环

发布时间 2023-08-19 15:37:38作者: Qiansui

C - Don't be cycle

题意
给定一个 n 个顶点，m 条边的无向图，你需要删除图中的一些边使得图中不存在环
问你需要删除的最少边数？

思路
考虑连通块的生成树
一个由 n 个顶点组成的连通块最多只能有 n - 1 条边，不然就会成环。

那么对于本题，我们只需要找到每个连通块的顶点数，那么每个连通块的保留边数已知，最后利用总边数减去保留边数即为答案。

或者说，最终的答案也就是 边数 - 顶点数 + 连通块个数。因为每一个连通块的保留边数 = 总顶点数 - 1，那么对于所有的连通块求和就是上面的式子。

所以这题可以利用 DFS、BFS、并查集等做即可。并查集可以模拟加边操作，当加入的边构成环时这条边就可以删除，统计这样的边数即为答案。

代码

  • BFS
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> e[n + 1];
	for(int i = 0; i < m; ++ i){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	vector<bool> vis(n + 1, false);
	queue<int> q;
	int ans = 0, c;
	for(int i = 1; i <= n; ++ i){
		if(!vis[i]){
			c = 0;
			q.push(i);
			while(!q.empty()){
				int u = q.front(); q.pop();
				if(vis[u]) continue;
				++ c;
				vis[u] = true;
				for(auto v : e[u]){
					if(!vis[v]){
						q.push(v);
					}
				}
			}
			ans += c - 1;
		}
	}
	cout << m - ans << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}
  • DSU
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

struct DSU{
	int num;
	vector<int> fa;
	DSU(int x = maxm) : num(x), fa(x + 1){
		for(int i = 0; i <= x; ++ i) fa[i] = i;
	}
	int findfa(int x){//迭代实现，用于数范围大时
		while (x != fa[x]) x = fa[x] = fa[fa[x]];
		return x;
	}
	// int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }//递归实现，压缩路径
	void merge(int u, int v){
		fa[findfa(u)] = findfa(v); return ;
	}
	bool same(int u, int v){ return findfa(u) == findfa(v); }
};

void solve(){
	int n, m;
	cin >> n >> m;
	DSU dsu(n);
	int ans = 0;
	for(int i = 0; i < m; ++ i){
		int u, v;
		cin >> u >> v;
		if(dsu.same(u, v)) ++ ans;
		dsu.merge(u, v);
	}
	cout << ans << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}