关注
求助大佬,第五题用并查集解的代码,通过率总是33.3%,帮忙看看哪里错了,网络主播红人那道题, #include <iostream> #include <vector> #include <algorithm> #include<sstream> #include<string> using namespace std; typedef vector<pair<int, int> > RangeList; class UnionSet { public: UnionSet(int n ) { _set=new int[n]; for(int i=0;i<n+1;i++){ _set[i]=-1; } _n = n; } int GetRoot(int p) { while (_set[p] >= 0) //最终的根应该小于0 { p = _set[p]; } return p; } void UnionFriends(int p1, int p2) { //获取p1和p2最终属于哪个朋友圈 int root1 = GetRoot(p1); int root2 = GetRoot(p2); //将本该属于同一个朋友圈的两个朋友圈合并 if (root1 != root2) { _set[root1] = _set[root1] + _set[root2]; _set[root2] = root1; } } int friends(int n, int m, RangeList& r) { int count = 0; //朋友圈的个数 //合并朋友圈 for (int i = 0; i < m; i++) { UnionFriends(r[i].first, r[i].second); } //计算朋友圈个数 for (int i = 1; i < n + 1; i++) //跳过0号下标,没有第0个人 { if (_set[i] < 0) count++; } return count; } private: int *_set; int _n; }; int main() { RangeList intervals; int n, duisum, start, end; cin>>n>>duisum; for (int i = 0; i < duisum; ++i) { cin >> start >> end; intervals.push_back(make_pair(start, end)); } int m=intervals.size(); UnionSet us(n); int ret = us.friends(n, m, intervals); cout <<ret << endl; }
查看原帖
点赞 1
相关推荐
09-14 22:53
中北大学 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 哪些公司真双非友好? #
28852次浏览 133人参与
# 4399求职进展汇总 #
32851次浏览 189人参与
# 深信服秋招来了 #
266592次浏览 2900人参与
# 牛友们的论文几号送审 #
55963次浏览 817人参与
# 秋招感动瞬间 #
33918次浏览 317人参与
# 应届生第一份工作最好去大厂吗? #
32556次浏览 575人参与
# 思朗科技求职进展汇总 #
61592次浏览 432人参与
# 今年秋招还有金九银十吗 #
2820次浏览 27人参与
# 你们公司哪个部门最累? #
32159次浏览 233人参与
# 工作后会跟朋友渐行渐远吗 #
40823次浏览 296人参与
# 阿里云工作体验 #
25756次浏览 100人参与
# 大厂面试初体验 #
56484次浏览 275人参与
# 德州仪器求职进展汇总 #
11586次浏览 162人参与
# 贝壳求职进展汇总 #
30887次浏览 173人参与
# 机械人的薪资开到多少,才适合去? #
128641次浏览 473人参与
# 技术转行的心路历程 #
61818次浏览 693人参与
# 你会为了工作牺牲生活吗? #
47329次浏览 376人参与
# 签约有哪些注意事项 #
47632次浏览 273人参与
# 机械人,你拿到几个offer啦 #
48227次浏览 355人参与
# 海尔求职进展汇总 #
10618次浏览 37人参与
# 毕业季,给职场新人一些建议 #
122750次浏览 2032人参与
# 找工作时的取与舍 #
98224次浏览 755人参与