URAL 1671 Anansi's Cobweb (并查集)
2024-08-23 04:34:23
题意:给一个无向图。每次查询破坏一条边,每次输出查询后连通图的个数。
思路:并查集。逆向思维,删边变成加边。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<iostream> #define inf -100000000 #define LL long long #define maxn 100005 using namespace std; struct Edge { int x,y; }; int parent[maxn]; int findset(int p) { return (parent[p]==p)?p:(parent[p]=findset(parent[p])); } Edge edge[maxn]; int query[maxn]; bool build[maxn]; int ans[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(build,,sizeof(build)); ; i<=m; ++i) scanf("%d%d",&edge[i].x,&edge[i].y); int q; scanf("%d",&q); ; i<=q; ++i) { scanf("%d",&query[i]); build[query[i]]=true; } ; i<=n; ++i) parent[i]=i; ; ; i<=m; ++i) if(!build[i]) { int fa=findset(edge[i].x),fb=findset(edge[i].y); if(fa!=fb) parent[fa]=fb; } ; i<=n; ++i) if(findset(i)==i) cnt++; ; --i) { ans[i]=cnt; int fa=findset(edge[query[i]].x),fb=findset(edge[query[i]].y); if(fa!=fb) { parent[fa]=fb; cnt--; } } ; i<=q; ++i) ) printf("%d",ans[i]); else printf(" %d",ans[i]); printf("\n"); } ; }
最新文章
- jboss设置图片上传大小
- css用背景图来替换文字来达到隐藏文字的目的
- 解决安装完centos6.6之后/etc/sysconfig/目录下没有iptables 的问题
- Navi.Soft30.产品.DataWindowNet.操作手册
- JavaWeb学习之Servlet(四)----ServletConfig获取配置信息、ServletContext的应用
- Iframe刷新父窗口的几种方式
- gsoap框架下的onvif程序流程分析
- 零基础学习Linux(二)网页乱码问题
- Java API ——Scanner类
- TC2.0中怎样调用汇编程序
- 【HDOJ】3085 Nightmare Ⅱ
- .NET定时发送邮件
- hdu 5823 color II 状压dp
- 操作数组的工具类Arrays
- 201521123026 《java程序设计》 第九周学习总结
- 原子动作检测 A Better Baseline for AVA
- http协议与https协议
- 不重叠的线段 51nod
- hdu 5493 (2015合肥网赛) Queue
- MySQL升5.6引发的问题
热门文章
- [转]Android WebView播放视频(包括全屏播放),androidwebview
- 年轻人你活着不是为了看K线!
- 解决xshell 中文乱码
- 在线读取Mongodb数据库下载EXCEL文件
- CentOS 6.x安装配置
- 再不用担心DataRow类型转换和空值了(使用扩展方法解决高频问题)
- DataTable 转成字符串数组
- MATLAB时间序列预测Prediction of time series with NAR neural network
- iscroll4框架解析[webapp开发](转)
- Java:标示符 基本数据类型