LA 3644 - X-Plosives ( 也即UVA 1160)

LA看题请点击：传送门

题目大意就是如果车上存在 k 个简单化合物，正好包含 k 种元素，那么它们将有危险，此时你应该拒绝装车。要求输出没有装车的化合物。

把每个元素看成顶点，则一个简单化合物就是一条边。如果存在环形，那么组成环的化合物是危险的，否则就是安全的。

那么如何实现呢？

用并查集。

#include<cstdio>

const int MAXN=100000+10;

int p[MAXN];

int findset(int x)

{

	return x==p[x]? x:p[x]=findset(p[x]); //把父节点赋予，压缩路径

}

int main()

{

	int a,b;

	while(scanf("%d",&a)!=EOF)

	{

		for(int i=0;i<MAXN;i++)

			p[i]=i;

		int ans=0;

		while(a != -1 )

		 {

			 scanf("%d",&b);

			 a=findset(a);        //通过查找判断a,b是否在同一集合。

			 b=findset(b);

			 if(a==b)

				 ans++;

			 else

				 p[a]=b;

			 scanf("%d",&a);

		}

		printf("%d\n",ans);

	}

}

巴特西

LA 3644 - X-Plosives ( 也即UVA 1160)

最新文章

热门文章