uvaLive 3644：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1645
题意：：每个化合物都是有两种元素组成的，如果车上存在k个简单化合物时，如果它和已装车的化合物形成易燃物的话，你就应该拒绝装车，否则装车，输出没有装车的个数
题解：一开始以为是与车上所有的化合物，所以直接用数组模拟打了一发。后来发现，是只要和部分化合物在一起，如果满足易暴就不行。白书上是用并查集。发现，这样的转化思想很巧妙。化合物作为一条边连接两个点，然后只要判断所有的连通分量中是否出现环就可以了，直接用并查集判断环。并查集有很多的作用。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = ; int f[MAXN]; int find(int x){
if (x != f[x])
f[x] = find(f[x]);
return f[x];
} int main(){
int x,y;
while (scanf("%d",&x) != EOF){
for (int i = ; i < MAXN; i++)
f[i] = i;
int ans = ;
while (x != -){
scanf("%d",&y);
int fx = find(x),fy = find(y);
if (fx == fy)
ans++;
else f[fx] = fy;
scanf("%d",&x);
}
printf("%d\n",ans);
}
return ;
}
随机推荐
-
python基础
内容概要: 一.python2 or python3 目前大多使用python2.7,随着时间的推移,python3将会成为python爱好者的主流. python2和3区别: 1.PRINT IS ...
-
gridview里日期显示格式
Text='<%#Bind("EndDate","{0:yyyy-MM-dd}") %>'
-
Web API与国际化
软件国际化是在软件设计和文档开发过程中,使得功能和代码设计能处理多种语言和文化习俗,在创建不同语言版本时,不需要重新设计源程序代码的软件工程方法.这在很多成熟的软件开发平台中非常常见.对于.net开发 ...
-
（转）WPF控件开源资源
(转)WPF控件开源资源 Textbox Drag/Drop in WPFhttp://www.codeproject.com/Articles/42696/Textbox-Drag-Drop-in- ...
-
(转)JAVA AJAX教程第一章-初始AJAX
既然是认识AJAX,理论和实践相结合,这样让自己学的更快,理解更深入,我分一下几点: 1. 认识传统的同步交互方式和AJAX解决方案 2. AJAX使用到的技术 3. 实例体验AJAX 一.同步 ...
-
重命名nginx服务器
为了防止被黑客扫描到web服务器信息,通过相对应的web服务器信息找出对应的版本漏洞,从而对web服务器进行入侵,nginx虽然功能强大,但是也是软件,软件就可能会有漏洞,例如nginx-0.6.32 ...
-
HDU 4927
http://acm.hdu.edu.cn/showproblem.php?pid=4927 直接模拟会超时,要在纸上写写推公式 A[n]*C(0,n-1) - A[n-1]*C(1,n-1) + ...
-
android 基于百度地图api开发定位以及获取详细地址
一:百度地图开发必须要到百度开发平台android开发api下载相应的库,已经申请百度地图开发key. 二:新建项目baidumaplocation.设计main.xml文件这里注意的是MapView ...
-
Android textAppearance的属性设置及TextView属性详解
textAppearance的属性设置 android:textAppearance="?android:attr/textAppearanceSmall" android:tex ...
-
linux学习心态建设
为啥我们要学习Linux 技术的价值不在于这个技术有多么高超,而在于技术本身给我们带来什么价值,所以很多时候我们学习一个技术,不能盲目学,是为了使用这个技术,知道这个技术的使用场景,知道这个技术带来的 ...