LA - 3644 - X-Plosives

本文主要是介绍LA - 3644 - X-Plosives，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一些产品，每种产品由2种化合物合成，按顺序接收一些产品，若组成其中某些产品的化合物的种类数与这些产品的产品数相等，就要拒绝接收，因为可能爆炸，求要拒绝多少次。

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1645

——>>若加入的化合物与已存在的化合物构成了环，就该拒绝，用并查集解决即可。

#include <iostream>using namespace std;const int maxn = 100000 + 10;int fa[maxn], height[maxn];     //并查集的父亲数组与树的高度数组int find(int x)     //并查集找根函数
{return (fa[x] != x) ? find(fa[x]) : x;
}bool judge(int x, int y)        //并查集联合函数
{int new_x = find(x);int new_y = find(y);if(new_x == new_y) return 0;if(height[new_x] > height[new_y])       //当树 new_x 比树 new_y 高时fa[new_y] = new_x;else if(height[new_x] == height[new_y])     //当树 new_x 和树 new_y 一样高时{fa[new_y] = new_x;height[new_x]++;}elsefa[new_x] = new_y;      //当树 new_y 比树 new_x 高时return 1;
}int main()
{int a, b, i;while(cin>>a){for(i = 0; i < maxn; i++)       //并查集初始化{fa[i] = i;      //第个点自成一棵树height[i] = 1;      //只有自己，高度为1}int refuse_cnt = 0;while(a != -1){cin>>b;if(judge(a, b) == 0) refuse_cnt++;      //如果存在环的话，拒绝数+1cin>>a;}cout<<refuse_cnt<<endl;}return 0;
}

这篇关于LA - 3644 - X-Plosives的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---