关注
求助大佬,第五题用并查集解的代码,通过率总是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
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
10909次浏览 148人参与
# 第一次面试 #
1072784次浏览 13736人参与
# 牛客AI体验站 #
17240次浏览 297人参与
# 投递几十家公司,到现在0offer,大家都一样吗 #
329211次浏览 2127人参与
# 你喜欢工作还是上学 #
89945次浏览 888人参与
# 被AI治愈的瞬间 #
91164次浏览 690人参与
# 有必要和同事成为好朋友吗? #
1880次浏览 34人参与
# 虾皮求职进展汇总 #
378415次浏览 2795人参与
# 百度求职进展汇总 #
667805次浏览 6293人参与
# 招聘要求与实际实习内容不符怎么办 #
169584次浏览 926人参与
# 如果不上班,你会去做什么 #
29513次浏览 466人参与
# 非技术岗薪资爆料 #
491529次浏览 3047人参与
# 你找工作的时候用AI吗? #
173864次浏览 893人参与
# 产品薪资爆料 #
159025次浏览 855人参与
# 你觉得什么岗位会被AI替代 #
41770次浏览 283人参与
# 考研失败就一定是坏事吗? #
222615次浏览 1543人参与
# 国企vs私企,你更想去? #
320198次浏览 2530人参与
# 我的求职精神状态 #
431974次浏览 3082人参与
# 秋招想进国企该如何准备 #
127617次浏览 620人参与
# 卷__卷不过你们,只能卷__了 #
42414次浏览 669人参与