UVa 1160 X-Plosives (并查集)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
要安全，这个“图”至多是一颗树（n个点，n-1条边），所以每次判断新加入的两个元素a,b是否都在树上，若是，则加入后树变图（n个点，n条边），此时应拒绝，否则合并a,b
完整代码：
/*0.015s*/
#include <cstdio>
#include<cstring>
const int mx = 100005;
int fa[mx], rk[mx];
int find(int x) {return ~fa[x] ? fa[x] = find(fa[x]) : x;}
///其实不用启发式合并也行，毕竟数据量超小
void merge(int x, int y)
{
if (rk[x] < rk[y]) fa[x] = y;
else
{
fa[y] = x;
if (rk[x] == rk[y]) ++rk[x];
}
}
int main()
{
int x, y;
while (~scanf("%d", &x))
{
memset(fa, -1, sizeof(fa));
memset(rk, 0, sizeof(rk));
int refusals = 0;
while (x != -1)
{
scanf("%d", &y);
x = find(x), y = find(y);
if (x == y) ++refusals; /// 如果x和y在同一个集合，则拒绝
else merge(x, y); /// 否则合并
scanf("%d", &x);
}
printf("%d\n", refusals);
}
return 0;
}| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |