【bzoj4579】[Usaco2016 Open]Closing the Farm 并查集
The open 查集
2023-09-11 14:22:40 时间
题目描述
Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.The farm consists of NN barns connected with MM bidirectional paths between some pairs of barns (1≤N,M≤200,000). To shut the farm down, FJ plans to close one barn at a time. When a barn closes, all paths adjacent to that barn also close, and can no longer be used.FJ is interested in knowing at each point in time (initially, and after each closing) whether his farm is "fully connected" -- meaning that it is possible to travel from any open barn to any other open barn along an appropriate series of paths. Since FJ's farm is initially in somewhat in a state of disrepair, it may not even start out fully connected.
输入
The first line of input contains N and M. The next M lines each describe a path in terms of the pair of barns it connects (barns are conveniently numbered 1…N). The final N lines give a permutation of 1…N describing the order in which the barns will be closed.
输出
The output consists of N lines, each containing "YES" or "NO". The first line indicates whether the initial farm is fully connected, and line i+1 indicates whether the farm is fully connected after the iith closing.
样例输入
4 3
1 2
2 3
3 4
3
4
1
2
样例输出
YES
NO
YES
YES
题目大意
给你n个点和m条边的无向图,有n次删点操作,删掉点后与这个点相连的边也随之删除。问删除每个点之前这个图是不是连通图。
题解
并查集
由于删点比较难搞,所以我们需要换一种思路:
可以先把所有的点删掉,然后反过来一个一个再加进来。
这样便于直接处理改动的边。
然后用一个并查集维护连通块即可。
#include <cstdio> int head[200010] , to[400010] , next[400010] , cnt , a[200010] , f[200010] , ans[200010] , ok[200010]; int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void add(int x , int y) { to[++cnt] = y; next[cnt] = head[x]; head[x] = cnt; } int main() { int n , m , i , j , x , y , tmp = 0; scanf("%d%d" , &n , &m); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]); for(i = 1 ; i <= n ; i ++ ) f[i] = i; for(i = n ; i >= 1 ; i -- ) { ok[a[i]] = 1; tmp ++ ; for(j = head[a[i]] ; j ; j = next[j]) { if(ok[to[j]]) { x = find(a[i]) , y = find(to[j]); if(x != y) { f[x] = y; tmp -- ; } } } ans[i] = (tmp == 1); } for(i = 1 ; i <= n ; i ++ ) printf("%s\n" , ans[i] ? "YES" : "NO"); return 0; }
相关文章
- node - DeprecationWarning: Mongoose: `findOneAndUpdate()` and `findOneAndDelete()` without the `use
- 【异常】The dependencies of some of the beans in the application context form a cycle
- [!Typescript] Tips: dynamic specify the type of arguments to function
- [AWS] Launch the VPC Wizard
- [Vue + TS] Watch for Changes in Vue Using the @Watch Decorator with TypeScript
- [Algorithms] The Bayes Rule
- [Node.js] Initialize a LoopBack Node.js Project through the CLI
- [Javascript + rxjs] Introducing the Observable
- [Cloud Architect] 12. Defensive Security in the Cloud
- [Tools Vim] Open Files into Vim from the Terminal as buffers, splits, and tabs
- [Cypress] Use the Most Robust Selector for Cypress Tests
- [React] Write a stateful Component with the React useState Hook and TypeScript
- [Algorithm] Given the root to a binary tree, return the deepest node
- [React Native] Animate the Scale of a React Native Button using Animated.spring
- [Angular2 Router] Optional Route Query Parameters - The queryParams Directive and the Query Parameters Observable
- VM启动报错Cannot open the disk,Failed to lock the file
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- GcExcel 4.0.2 for Java and C# The Crack
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- 成功解决The following specifications were found to be incompatible with the existing python installation
- POJ1163 The Triangle 【DP】
- Caused by: org.xml.sax.SAXParseException; systemId: file:/home/hadoop/hive-0.12.0/conf/hive-site.xml; lineNumber: 5; columnNumber: 2; The markup in the document following the root element must be well
- 【问题解决】The connection to the server localhost:8080 was refused
- The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar
- Testing in the Cloud:使用TPT进行云端测试
- 爆炸几何之 CCPC网络赛 I - The Designer (笛卡尔定理)
- 【训练过程】2) Train the VAEs of domain A and domain B respectively(分别训练域A和域B的VAE)