比赛 20120712 评测结果 AAAAAAAAAA
题目名称 爆炸化合物 最终得分 100
用户昵称 沉迷学习的假的Keller 运行时间 0.132 s
代码语言 C++ 内存使用 2.99 MiB
提交时间 2016-02-17 09:12:37
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[100000+10],d[100000+10],sz[500000+10];
int find(int x){
	if(f[x]==x){
		return x;
	}
	else {
		int fx=find(f[x]);
		//d[x]+=d[fx];
		return f[x]=fx;
	}
}
int main(){
	freopen("explosion.in","r",stdin);
	freopen("explosion.out","w",stdout);
	int a,b;
	for(int i=1;i<=100000+10;i++){
		f[i]=i;
		sz[i]=1;
	}
	int ans=0;
	while(1){
		scanf("%d",&a);
		if(a==-1){
			break;
		}
		scanf("%d",&b);
		int fx=find(a),fy=find(b);
		if(fx!=fy){
			f[fy]=fx;
			//d[fx]+=sz[fy];
			//sz[fy]+=sz[fx];
		}
		else{
		    //if(sz[a]==d[a]||sz[b]==d[b])
				ans++;
		}
	}
	printf("%d",ans);
	return 0;
}