题解 | #第一题#

第一题

http://www.nowcoder.com/practice/7c29cdfa28274c86afc9e88c07448a10

耍赖皮,用散列表

#include <cstdio>
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

unordered_map<int, int> parent;
vector<int> v;

int Find(int x){
	if(!parent.count(x)){
		return x;
	}
	return Find(parent[x]);
}

void Union(int x, int y){
	x = Find(x);
	y = Find(y);
	if(x != y){
		parent[y] = x;//暴力一点,省事 
	}
}

int main(){
	int x, y;
	while(scanf("%d%d", &x, &y) != EOF){
		v.push_back(x);
		Union(x, y);
	}
	int cnt = 0;
	sort(v.begin(), v.end());
	for(int i=0; i<v.size(); i++){
		if(i && v[i] == v[i-1]){
			continue;
		}
		if(!parent.count(v[i])){
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}
全部评论

相关推荐

07-02 13:52
武汉大学 golang
骗你的不露头也秒
牛客87776816...:😃查看图片
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
07-02 13:52
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务