UVA 1160 X-Plosives（算法竞赛训练指南，并查集）

并查集， 算法竞赛训练指南， 191页
题目意思：
所以的元素看做是顶点，每两点连线，如果图中存在环的话，就会爆炸

本题要点：
1、每次读入 a, b, 如果 a 和 b 在同一个集合，就舍弃这两点。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 100010;
int a[MaxN], b[MaxN], fa[MaxN];
int k, cnt;int get(int x)
{
    if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}void merge(int x, int y)
{
    int fax = get(x), fay = get(y);if(fax != fay){
    fa[fay] = fax;}
}void solve()
{
    for(int i = 0; i < MaxN; ++i){
    fa[i] = i;}int refuse = 0;		for(int i = 0; i < cnt; ++i){
    if(get(a[i]) != get(b[i])){
    merge(a[i], b[i]);}else{
    ++refuse;}}printf("%d\n", refuse);
}int main()
{
    cnt = 0;while(scanf("%d", &k) != EOF){
    if(k == -1)	//计算{
    solve();cnt = 0;}else{
    a[cnt] = k;	scanf("%d", &b[cnt++]);}}return 0;
}/* 1 2 3 4 3 5 3 1 2 3 4 1 2 6 6 5 -1 *//* 3 */