P3535 [POI2012] TOU-Tour de Byteotia

本文主要是介绍P3535 [POI2012] TOU-Tour de Byteotia，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[P3535 POI2012] TOU-Tour de Byteotia - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

用并查集进行判环。先将$u\ge k$且$v\ge k$的边进行合并。之后再遍历一遍全部边，若边中点存在小于等于$k$的，如果两点父结点指向不同不用删除并进行合并，否则需要进行删除。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 21;
int fa[N];
struct no {int u,v;
}a[N];
void init(int n) {for(int i = 1; i <= n; ++i) fa[i] = i;
}
int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]); }
void merge(int u, int v) {int fu = find(u), fv = find(v);if(fu != fv) fa[fu] = fv;
}
int main()
{int n,m,k; cin>>n>>m>>k;init(n);for(int i = 0,u,v; i < m; ++i) {cin>>u>>v;a[i] = {u,v};if(u > k && v > k) merge(u, v), a[i].u = -1;}int res = 0;for(int i = 0; i < m; ++i) {if(a[i].u == -1) continue;if(find(a[i].u) != find(a[i].v)) merge(a[i].v, a[i].u);else res++;}cout<<res;
}

这篇关于P3535 [POI2012] TOU-Tour de Byteotia的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---