并查集 LA 3644

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

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1645

题意理解错，TMD，   WA的哭了一下午

k种化合物如果有k种元素，会爆炸，  意思是  假设现在有n种元素，那么其中如果存在k种化合物如果有k种元素（k<=n）就不可以！！！

刘汝佳的说法还是很有意思的：元素当点，边表示化合物，那么一旦出现环，就是k种化合物如果有k种元素的情况，蛮巧妙的。

贴代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>using namespace std;#define MAXN 100011int father[MAXN+2];
int num;void makeset()
{for(int i=0;i<=MAXN;i++){father[i]=i;}
}int Find(int x)
{if(x!=father[x])return father[x]=Find(father[x]);return x;
}void Union(int x,int y)
{x=Find(x);y=Find(y);father[y]=x;num++;
}int main()
{int a,b,t,ans,tmp;while(scanf("%d",&a)!=EOF){num=0;t=0;ans=0;makeset();while(a!=-1){scanf("%d",&b);//t++;//tmp=num;//int m=Find(flag);int n=Find(a);int o=Find(b);if(n!=o)Union(n,o);elseans++;scanf("%d",&a);}printf("%d\n",ans);}return 0;
}

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

---