題意：給定一些化合物（含有兩個(gè)元素），當(dāng)滿足k個(gè)化合物且有k個(gè)元素的時(shí)候會(huì)發(fā)生爆炸，問(wèn)多少個(gè)化合物是不能裝車的。

思路：并查集的簡(jiǎn)單應(yīng)用。實(shí)際上滿足條件的時(shí)候是一個(gè)環(huán)，因此用并查集簡(jiǎn)單判環(huán)即可。

code：

#include <bits/stdc++.h> using namespace std;const int N=1e5+5; int fa[N]; int getfa(int x){return fa[x]!=x?fa[x]=getfa(fa[x]):x;}int main() {int x,y;while (~scanf("%d",&x)){for (int i=0;i<N;i++) fa[i]=i;int res=0;while (x!=-1){scanf("%d",&y);x=getfa(x);y=getfa(y);if (x==y) ++res;else fa[x]=y;scanf("%d",&x);}printf("%d\n",res);} }

總結(jié)

以上是生活随笔為你收集整理的UVA 1160——X-Plosives的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。