第五题代码通过率总是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;
}