记录编号	306997	评测结果	AAAAAAAAAA
题目名称	爆炸化合物	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2016-09-13 16:24:15	内存使用	0.60 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int findroot(int);
void mergeset(int,int);
int x,y,prt[maxn],ans=0;
int main(){
#define MINE
#ifdef MINE
	freopen("explosion.in","r",stdin);
	freopen("explosion.out","w",stdout);
#endif
	for(int i=1;i<=100000;i++)prt[i]=i;
	while(scanf("%d%d",&x,&y)==2){
		if(findroot(x)==findroot(y))ans++;
		else mergeset(x,y);
	}
	printf("%d",ans);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
int findroot(int x){
	int rt=prt[x],y;
	while(prt[rt]!=rt)rt=prt[rt];
	while(prt[x]!=rt){
		y=prt[x];
		prt[x]=rt;
		x=y;
	}
	return rt;
}
void mergeset(int x,int y){
	int rx=findroot(x),ry=findroot(y);
	if(rx==ry)return;
	prt[rx]=ry;
}