NC212821小y的旅行

题意： 给定$n$点$m$条无向边，最少需要删除多少条边可以使得所有编号$\le k$的点都不在环上。 数据范围：$1\le n\le 10^6,1\le m\le 2\times 10^6,1\le k\le n$

题解： 构造生成树。

先用所有编号大于$k$的点连成的边构造生成树。然后用所有存在编号$\le k$的边来构造生成树。当无法加入时，说明该边需删除，否则该边加入生成树即可。

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<stack> #include<queue> #include<map> #include<vector> #include<cmath> using namespace std; typedef long long ll; template<typename T> inline T Read(){ T s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();} return s * f; } #define read() Read<int>() #define readl() Read<long long>() const int N = 1e6 + 10, M = 2e6 + 10; int p[N]; struct Node{ int a, b; bool operator < (const Node &A) const { return a > A.a; } }e[M]; int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; } void solve() { int n = read(), m = read(), k = read(); int res = 0; for(int i = 1; i <= n; i++) p[i] = i; for(int i = 1; i <= m; i++) { int a = read(), b = read(); if(a > b) swap(a, b); e[i] = {a, b}; } sort(e + 1, e + m + 1); for(int i = 1; i <= m; i++) { int a = e[i].a, b = e[i].b; int fa = find(a), fb = find(b); if(fa != fb) p[fa] = fb; else if(a <= k) ++res; } printf("%d\n", res); } int main() { int T = 1; //T = read(); for(int i = 1; i <= T; ++i) { solve(); } return 0; }