关注
求助大佬,第五题用并查集解的代码,通过率总是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
相关推荐
点赞 评论 收藏
分享

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 假如你的老板掉河里,你的工作能为他做什么 #
30824次浏览 376人参与
# 学历贬值真的很严重吗? #
25509次浏览 178人参与
# 你觉得早上几点上班合适? #
73126次浏览 307人参与
# 听劝,这个公司值得去吗 #
487097次浏览 1709人参与
# 第一份工作应该选高薪还是热爱? #
68453次浏览 648人参与
# 秋招签约后的心态变化 #
83347次浏览 819人参与
# 双非能在秋招上岸吗? #
222620次浏览 1178人参与
# 推荐一首陪你工作的歌吧 #
14900次浏览 99人参与
# 打工人的工作餐日常 #
54220次浏览 426人参与
# 月薪多少能在一线城市生存 #
33184次浏览 340人参与
# 大学最后一个寒假,我想…… #
47063次浏览 576人参与
# 26届的你们有几段实习? #
47906次浏览 521人参与
# 外包能不能当跳板? #
37444次浏览 227人参与
# 你上一次加班是什么时候? #
89389次浏览 574人参与
# 你以为的实习VS真实的实习 #
33405次浏览 300人参与
# 2023毕业生求职有问必答 #
181645次浏览 1626人参与
# 哪些公司真双非友好? #
16335次浏览 82人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92753次浏览 684人参与
# 追觅科技求职进展汇总 #
18722次浏览 120人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
118483次浏览 814人参与