UVa 1160

X-Plosives

from Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

Problem

一个秘密机构研究了一种特殊的爆炸物，这种爆炸物由两种不同的化合物组成，叫做 binding pair 。不同的binding pairs可能由不同的化合物组成，当N(N > 2)种不同的的binding pairs包含了N种不同的化合物时，就会产生强大的爆炸力。举例来说，当有三种binding pairs，分别是A+B，B+C，A+C（3种pair含有3种化合物），就会发生爆炸；而A+B，B+C，A+D（3种pair含有4种化合物），就不会发生爆炸。

你是一个送货员，在运送这些binding pairs的时候应该防止他们爆炸，因此当binding pairs被按顺序送上来之后，你应该懂得判断：当某个binding pair装上车后会发生爆炸时，你应该拒绝将这个binding pair装箱。例如，当你按顺序接收A+B，G+B，D+F，A+E，E+G，F+H这些binding pair时，你应该只接受前四个，拒绝第五个，然后接受最后一个。

给你一个binding pair的序列，输出你会拒绝装箱的binding pair的个数。

Solution

把每种化合物看做顶点，则每个binding pair就是一条边。当构造图的过程中出现环的时候，就会发生爆炸，则应该拒绝。要知道图中是否出现了环，我们可以利用并查集来维护图的连通分量集合，每次得到一个binding pair（A+B）的时候，检查A和B是否在同一集合中。如果是，则拒绝，反之则接受。

该算法的时间复杂度为 O(N) 。