1013 Battle Over Cities(并查集解法)
关于背景的介绍见1013 Battle Over Cities(图的DFS解法)
DFS就是不算特定结点后数连通子图的总数，再减一。我想着那么并查集就是数不算特定节点后，集合元素(根)的个数。但是我弄错了一件事，我是边输入，边合并，然后对于每一个占领城市的输入，再绕过那座城市，这样是会出问题的，因为被占领城市很可能被算作了根节点。
正确做法是：依然设置一个邻接表，对于每个占领城市的输入，绕开它把其他存在边的结点合并，再数集合元素的个数，最后减一。
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long LL;using namespace std;const int maxn = 1010;//总城市数上限 int allCityNum,lostIdx;vector<int> G[maxn];int F[maxn];void initF(){for(int i=1;i<=allCityNum;i++)F[i] = i;
} int findSo(int x){int a = x;while(x!=F[x]){x = F[x];}while(a!=F[a]){int z = a;a = F[a];F[z] = x;}return x;
}void unite(int a,int b){int sa = findSo(a);int sb = findSo(b);if(sa!=sb){F[sa] = sb;}
}int main(){int wayNum,lostCityNum;scanf("%d %d %d",&allCityNum,&wayNum,&lostCityNum);for(int i=0;i<wayNum;i++){int ct1,ct2;scanf("%d %d",&ct1,&ct2);G[ct1].push_back(ct2);G[ct2].push_back(ct1);}set<int> roots;for(int i=0;i<lostCityNum;i++){scanf("%d",&lostIdx);initF();roots.clear();for(int j=1;j<=allCityNum;j++){if(j==lostIdx)continue;for(int k=0;k<G[j].size();k++){int u = G[j][k];if(u!=lostIdx)unite(j,u);} }for(int j=1;j<=allCityNum;j++){if(j!=lostIdx){int sj = findSo(j);roots.insert(sj);}}printf("%d\n",roots.size()-1);}return 0;
}相关文章：
FastDFS为什么要结合Nginx？
为什么选择Nginx Nginx 是一个很牛的高性能Web和反向代理服务器, 它具有有很多非常优越的特性: 在高连接并发的情况下，Nginx是Apache服务器不错的替代品: Nginx在美国是做虚拟主机生意的老板们经常选择的软件平台之一. 能够支持高达 50,000 个并发连接数的响应, 感谢…
STL容器[34]
SERVER以读打开FIFO；CLIENT以写打开FIFO；SERVER关闭FIFO；CLIENT向当前FIFO写数据，此时CLIENT获得一个SIGPIPE信号。如果忽略该信号，那么write将返回-1，ERRNO为EPIPE向一个写打开，当对端已经关闭…
企业可视化报表工具选型经验分享
选型背景 我们是一家面向金融行业的系统集成商，每年要做十几个项目（看得出来我们并不大/笑哭），项目分大小、做事分先后，可不管怎样都绕不开数据，数据处理经常占项目的大头，所以经常会选择一些市…
1003 Emergency(Dijkstra，Bellman-Ford，SPFA三种解法)
目录 1. Dijkstra解法 2. Bellman-Ford解法 3. SPFA解法 4. Dijkstra解法AC代码 5. Bellman-Ford解法AC代码 6. SPFA解法AC代码 1. Dijkstra解法 这题不仅涉及到基础的解法，还涉及到第二标准(累计军队数量)，以及还要记录最短路径条数。这些都是在…
存储过程4-前台
代码 ALTERproc[dbo].[P_CheckCode](retintoutput,nIdint,tagnvarchar(50),cCodenvarchar(50),nHotelIdint)asbeginifUpper(tag)B_AREAbeginifexists(select1fromB_Area wherecCodecCodeandnHotelIdnHotelIdandnId<>nId) setret1elsesetret-1endelseifUpper(t…
安卓学习-其他-文件读写
在android中的文件放在不同位置，它们的读取方式也有一些不同。 本文对android中对资源文件的读取、数据区文件的读取、SD卡文件的读取及RandomAccessFile的方式和方法进行了整理。供参考。 一、资源文件的读取： 1) 从resource的raw中读取文件数据&#x…
X5同层播放器应用实践
移动端浏览器中的video元素是比较特别的，早期无论是在iOS还是Android的浏览器中，它都位于页面的最顶层，无法被遮挡。后来，这个问题在iOS下得到了解决。但是对Android的大部分浏览器来说，问题仍然存在。X5是腾讯基于Web…
1007 Maximum Subsequence Sum(两种思路)
1.解法1 思路 对于动态规划来说，最关键的就是找到状态转移方程，本题设置一个前向数组，元素predp[i]表示的是以元素i结尾的连续数列和的最大值，转移方程是predp[i] max(predp[i-1]a[i],a[i])。要做的事就是完成这个dp数组&#x…
C#学习-EF在三层中使用
1.搭建普通三层 DAL层，BLL层，Model层，Web层； DAL层引用Model层 BLL层引用DAL层和Model层 Web层引用BLL层和Model层 2.实现EF三层的搭建（添加引用，修改配置信息） 2.1添加EF对象 在Model中添加一个…
各大IT公司笔试真题汇总开发人员一定要加入收藏夹的网站(收藏)
巨人网络java笔试基础题分享 http://www.coderarea.net/bbs/read.php?tid834 百度笔试题 http://www.coderarea.net/bbs/read.php?tid811 百度2010校招运维部门笔试 http://www.coderarea.net/bbs/read.php?tid779 百度2010年校园招聘软件测试笔试题 http://www.coderarea.n…
Python编写Hive UDF
2019独角兽企业重金招聘Python工程师标准>>> 1. 目的 从string类型的字段中解析并汇总每种category类型的总amount 2. 素材 表名：test_table order_no hotel_seq discount_detail D8662EF4E 10212527 NULL 45C024849 …
1045 Favorite Color Stripe(LIS解法)
解题思路 本题属于Longest Increasing Sequence最长不下降子序列，但是要注意，LIS当中不会有无效的元素，而本题是有的，所以先要把无效元素过滤掉，才能转化成为LIS问题。 这里用到了hashTable(用map更慢)，初…
5.8fork父子进程
实验4-2：fork父子进程 实验目的： 理解fork创建子进程的本质 实验要求： 1、按如下要求编写程序: （1）、打开一个有内容的文件; （2）、调用fork创建子进程; （3）、读文件…
word表格自动编号
选中全部内容--右键--项目符号和编号--自定义--编号样式--选01,02样式.则生成所有编号选中第二批编号,--重新编号,就又从01开始了转载于:https://www.cnblogs.com/wzshhynk/archive/2009/12/30/1635805.html
Vue API(directives) 自定义指令
前言：除了vue的内置指令以外，我们可以定义自定义指令。内置指令表相见：https://www.cnblogs.com/ilovexiaoming/p/6840383.html 我们定义一个最简单的 <script> export default {name: App,data(){return{yanse:red}},// 所有自定义指令…
1045 Favorite Color Stripe(LCS解法) 需再理解
解题思路 使用LCS方法解这一题，首先要把现有的颜色和Eva的颜色看成即将取材的序列s和e。 而且注意2个序列都要从1开始读入，因为递归边界（待后叙）。 dp[i][j]代表的是e[1]-e[i]和s[1]-s[j]的范围内，公共子序列的长度…
C++ primer第五版随笔--2015年1月6日
记录自己看这本书时的一些内容。 一、引用（reference） 引用为对象起了另外一个名字。例如： int ival1024； int &relVal1ival;//对，注意尽量不要用这方式：int& relvalival； int &rel…
Python性能分析指南——中
程序使用了多少内存？现在我们对计时有了较好的理解，那么让我们继续弄清楚程序使用了多少内存。我们很幸运，Fabian Pedregosa模仿Robert Kern的line_profiler实现了一个不错的内存分析器。首先使用pip安装:这里建议安装psutil包，因…
1040 Longest Symmetric String 需再做
解题思路 本题属于最长回文子串专题下。与之前的LIS和LCS的动规有两个较大的不同 1. 虽然最后也是要求长度，但是长度信息不再蕴含在dp数组当中，dp[i][j]表示的仅仅是从s[i]起s[j]止这一段是否是回文，所以为了提醒自己，我设置成了…
回顾2009，展望2010。
回顾2009，展望2010。 2009即将过去，总结2009年，计划2010年。 2009年12月31日。转载于:https://www.cnblogs.com/finehappy/archive/2009/12/31/1654975.html
Linux Mint 19 安装Gnome Boxes 新建失败
之前在Ubuntu论坛提出，一直没有解决.http://forum.ubuntu.org.cn/viewtopic.php?f65&t488821 后参照： https://askubuntu.com/questions/836703/ ... sue/836715对方报错： (gnome-boxes:15984): Boxes-WARNING **: wizard.vala:463: Fai…
1057 Stack
目录 解题思路 AC代码 解题思路 虽然题目的名字是栈，但是这题和栈的关系很小，甚至我都没有用到stack这个数据结构，而是用vector<int>的pop_back()来模拟栈的弹出。 主要考察的是：在线查询，也就是查询过程中…
【译】使用自定义ViewHelper来简化Asp.net MVC view的开发------part1
从开发者的角度来看，创建Asp.net MVC的View是一件很爽的事，因为你可以精确控制最终生成的HTML。具有讽刺意味的是不得不写出每一行HTML代码同时也是Asp.net MVC的View中让人不爽的地方。让我用我的一个经历来告诉我创建ASP.Net MVC view Helpers背后灵感…
看书挑剔,只看经典
如何选择经典，可以到网上做做功课，看看评价，综合分析一下。书籍是我们知识的主要来源。在选择书籍的时候做足功课是对我们自己时间的负责；这和在超市里买东西时对比各个品牌是一个道理；只不过奇怪的是，我很…
0-1背包使用一维dp数组时为何v要从大到小枚举
样例数据 5 8 3 5 1 2 2 4 5 2 1 3 如若不然，也就是让v按照从小到大的顺序枚举，就会出现 注意高亮的那一行，第一件物品的重量只有3，怎么会得到6呢？ 代码如下 #include<cstdio> #include<cmath> #inclu…
异步编程模型--使用 IAsyncResult 对象
先推荐阅读下面的资料：MSDN：异步编程设计模式IBM developerworks： 使用异步 I/O 大大提高应用程序的性能参考博文：1、正确使用异步操作 2、Lab：体会ASP.NET异步处理请求的效果 3、WCF中的异步调用 4、WCF从理论到实践(…
对XX证券报关于物联网操作系统的几个问题的答复
XX证券报提问了几个关于物联网和物联网操作系统的问题，个人表达了一些粗陋的观点，在这里发表出来，与行业朋友交流和探讨。物联网行业最需要解决的问题是什么？虽然物联网这个行业被炒得比较热，但是截至目前，…
Java基础 - 面向对象 - 构造方法
在类中除了成员方法之外，还存在一种特殊类型的方法，那就是构造方法。构造方法是一个与类同名的方法，对象的创建就是通过构造方法完成的。每当类实例化一个对象时，类都会自动调用构造方法。 构造方法的特点： 构造方法没…
1105 Spiral Matrix 给定数组向螺旋矩阵中填入数据
两个测试用例超时，可直接跳转到 目录 超时点1 超时点2 要做的事情是，将数组按照非升序/降序，顺时针从外围到内部一圈一圈地把数据填到矩阵中，并打印出来。也就是将数组排好序后，将矩阵的坐标和数组…
一晚上就能让你小腹变小的方法 - 健康程序员，至尚生活！
仅一晚上针对小腹的锻炼就会让它明显收紧，很不可思议吧？但它确实发生了。形体教练向我们推荐：做30次转身运动(双手抱在脑后站立，迅速分别向左右两侧依次扭转上肢，注意不要以膝盖为轴，使运动轴心保持在骨盆以…