【模拟赛】2021.8.14.B

本文主要是介绍【模拟赛】2021.8.14.B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给出一张n个点m条边的无向图和一个k，求若要使编号小于等于k的点不在环上需要删除多少条边

思路

首先肯定是只用删编号小于等于k的点的边
先把其他边全部连起来
然后枚举这些可能要删的边
用并查集判环，若两点find值相同，则这条边可以删
否则可以给他连起来

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int Fa[10000250], x[10000250], y[10000250];
int n, m, k, xx, yy, Ans;inline int read()
{int x = 0, r = 1; char c = getchar();while(c < '0' || c > '9'){if(c == '-')r = -1;c = getchar();}while('0' <= c && c <= '9')x = x * 10 + c - 48, c = getchar();return x * r;
}int find(int k)
{if(k == Fa[k])return k;else return (Fa[k] = find(Fa[k]));
}int main()
{n = read(), m = read(), k = read();for(int i = 1; i <= n; ++i)Fa[i] = i;for(int i = 1; i <= m; ++i){x[i] = read(), y[i] = read();if(x[i] > k && y[i] > k){xx = find(x[i]);yy = find(y[i]);Fa[max(xx, yy)] = min(xx, yy);}}for(int i = 1; i <= m; ++i)if(x[i] <= k || y[i] <= k){xx = find(x[i]);yy = find(y[i]);if(xx == yy)Ans++;else Fa[max(xx, yy)] = min(xx, yy);}printf("%d", Ans);return 0;
}

这篇关于【模拟赛】2021.8.14.B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---