LA 3644 易爆物 并查集

题目链接：

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

题意：有一些化合物，每种化合物中含有两种元素，如果有k种化合物含有K种元素就会爆炸，现在装车司机按照输入顺序一件一件的装，遇到加入后会爆炸的化合物就不装，问会有多少化合物不能被装入。

解法：将每种元素看成一个顶点，一个化合物含有两种元素就是一条边，构图完成后，出现环就意味着爆炸，所以用并查集，像Kruskal算法一样为同一连通分量的为同一个父节点，加入某种化合物，该化合物的两种元素已经连通，如果再加进来就会出现环。。。拒绝该化合物进入。

贴代码：

1 #include<cstdio> 2 #include<cstring> 3 const int N=100005; 4 int pa[N]; 5 int findset(int x) 6 { 7 return pa[x] == -1 ?x:x=findset(pa[x]); 8 } 9 int main() 10 { 11 // freopen("in.txt","r",stdin); 12 int cnt,x,y; 13 while(scanf("%d",&x) == 1) 14 { 15 cnt =0; 16 memset(pa,-1,sizeof(pa)); 17 while(x != -1) 18 { 19 scanf("%d",&y); 20 x = findset(x) ; 21 y = findset(y); 22 if(x==y ) ++cnt; 23 else pa[x]=y; 24 scanf("%d",&x); 25 } 26 printf("%d\n",cnt); 27 } 28 return 0; 29 } View Code

 

转载于:https://www.cnblogs.com/allh123/p/3287511.html

总结

以上是生活随笔为你收集整理的LA 3644 易爆物 并查集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。