关注
求助大佬,第五题用并查集解的代码,通过率总是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
相关推荐
查看14道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 给工作过的公司写一条大众点评,你会怎么写? #
1136次浏览 23人参与
# 牛油的搬砖plog #
189276次浏览 1272人参与
# 厦门银行科技岗值不值得投 #
16578次浏览 404人参与
# 烂工作和没工作哪个更痛苦? #
1699次浏览 46人参与
# 发工资后,你做的第一件事是什么 #
100315次浏览 336人参与
# AI替代不了什么? #
1682次浏览 39人参与
# 学历VS实习,哪个更重要? #
10063次浏览 157人参与
# 一人分享一道面试手撕题 #
114085次浏览 2872人参与
# 工作上你捅过哪些篓子? #
69265次浏览 334人参与
# 产品人求职现状 #
361335次浏览 2603人参与
# 谈薪时HR压价该怎么应对 #
294076次浏览 3361人参与
# 春招至今,你收到几个面试了? #
4167次浏览 43人参与
# 机械校招之路总结 #
120285次浏览 2083人参与
# 面试紧张时你会有什么表现? #
35757次浏览 243人参与
# 刚工作的你,踩过哪些坑? #
33330次浏览 278人参与
# uu们,春招你还来吗? #
69696次浏览 929人参与
# 面试中,你被问过哪些奇葩问题? #
99450次浏览 1429人参与
# 非技术投递记录 #
716827次浏览 6930人参与
# 你的实习什么时候入职 #
368219次浏览 2368人参与
# 牛友的志愿填报指南 #
63926次浏览 492人参与
# 实习生应该准时下班吗 #
349248次浏览 1752人参与
