牛客IOI周赛19-普及组 C.小y的旅行

题目链接

题意

n个点m条边的无向图，最少需要删除多少条边，使得编号$\le k$的点不在一个环上。

思路

采用并查集将编号都大于K的边进行合并，这样相当于将一些无关的边进行缩点，然后再进行一次并查集，找到剩余成环的边。

#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; }