题目名称 899. 爆炸化合物
输入输出 explosion.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2012-07-12加入
开放分组 全部用户
提交状态
分类标签
并查集
分享题解
通过:171, 提交:330, 通过率:51.82%
Gravatarcy 100 0.045 s 0.27 MiB C++
Gravatarcy 100 0.049 s 0.27 MiB C++
Gravatar521 100 0.049 s 0.43 MiB C++
GravatarHeHe 100 0.058 s 0.95 MiB C++
GravatarCandy? 100 0.071 s 0.70 MiB C++
GravatarONCE AGAIN 100 0.073 s 0.67 MiB C++
GravatarSPA 100 0.073 s 0.70 MiB C++
GravatarONCE AGAIN 100 0.081 s 0.70 MiB C++
Gravatar1020 100 0.081 s 1.46 MiB C++
Gravatar_Itachi 100 0.082 s 0.63 MiB C++
本题关联比赛
20120712
20120712
关于 爆炸化合物 的近10条评论(全部评论)
GravatarAntiLeaf
2017-05-25 15:42 18楼
GravatarNVIDIA
2016-09-13 16:40 17楼
突然发现这是《训练指南》上的题。。。
Gravatarliu_runda
2016-03-09 17:33 16楼
GravatarSPA
2016-03-07 16:36 15楼
数组开小了
GravatarSOBER GOOD BOY
2016-02-19 06:27 14楼
BOOM!Shakalaka~
Gravatar洛克索耶夫
2016-02-18 07:35 13楼
模拟不过= =
GravatarYGOI_真神名曰驴蛋蛋
2016-02-17 09:47 12楼
思路想了半天。。。最后发现其实就是一个无向图判环。若n个化合物能组成炸弹,那它们必能排列成(x1,x2)(x2,x3)....(xn,x1)的形式。因此就是用并查集对无向图判环,视化合物为边,边依次给出,不形成环的边添加进去,形成环的边不可添加。
Gravatarliu_runda
2016-02-17 08:58 11楼
回复 @miner :
666
GravatarHzoi_
2016-02-16 14:42 10楼
回复 @Alan :
路径压缩
GravatarSky_miner
2015-12-20 16:55 9楼

899. 爆炸化合物

★   输入文件:explosion.in   输出文件:explosion.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

各国都在加大力度防范恐怖份子对于飞机的袭击,X国也不例外,液体一律不准带上飞机。但是,X国最近打探到某恐怖分子集团正在密谋策划一项恐怖袭击,恐怖分子们准备使用固体材料来制造炸弹!
幸运的是,X国已经知道了恐怖分子们将使用某些特定的化合物来制造炸弹。每种化合物是由2种不同的不明元素构成的。如果将k个化合物放在一起,而这k个化合物恰好含有k种元素,那么这些化合物就构成了一个炸弹。


例如:现在有6个化合物A+B, G+B, D+F, A+E, E+G, F+H,其中A+B, G+B, A+E, E+G这4种化合物中恰好含有4种元素,因此这4种化合物如果在一起,那么就会构成炸弹。
现在,机场的安俭部分已经收到了若干个即将被带上飞机的化合物,这些化合物将依次上飞机,对于每个化合物,你需要判断该化合物能否上飞机。(即判断他与之前已经上飞机的化合物是否会构成炸弹)。对于上面的例子,第5个化合物将不能被带上飞机。

【输入文件】

给出若干行,每行两个整数a和b,表示该化合物的两种元素。输入的最后,用一个-1表示输入文件结束。

【输出文件】

一行,表示有多少个化合物不能上飞机。

【样例输入】
1 2
3 4
3 5
3 1
2 3
4 1
2 6
6 5
-1
【样例输出】
3


【数据规模】
对于100%的数据:
元素的标号是一个[0,10^5]的整数。
最多有10^5个化合物。