題目鏈接

題意

n個(gè)點(diǎn)m條邊的無(wú)向圖，最少需要?jiǎng)h除多少條邊，使得編號(hào)$\le k$的點(diǎn)不在一個(gè)環(huán)上。

思路

采用并查集將編號(hào)都大于K的邊進(jìn)行合并，這樣相當(dāng)于將一些無(wú)關(guān)的邊進(jìn)行縮點(diǎn)，然后再進(jìn)行一次并查集，找到剩余成環(huán)的邊。

#include <bits/stdc++.h> using namespace std; const int N = 1000001; int fa[N]; int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]); } int main() {int n, m, k;cin >> n >> m >> k;int l, r, ret = 0;vector<pair<int,int>> edge;for (int i = 1; i <= n; ++i) fa[i] = i;while (m--) {cin >> l >> r;if (l > k && r > k) {fa[find(l)] = find(r);}else {edge.push_back({l, r});}}for (auto it : edge) {int fx = find(it.first);int fy = find(it.second);// cout << fx << " " << fy << " " << it.first << "-" << it.second << endl;if (fx == fy) ret++;else fa[fx] = fy;}cout << ret << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客IOI周赛19-普及组 C.小y的旅行的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。