武松日记# Joke - 肚皮舞运动
e*8
1 楼
求指点。。。
我的代码，不知道为什么所有的case都可以过，就是第１１个test case怎么都过不了
，不解啊不解 >_用的是union-find的数据结构，CLRS书上的算法
想法就是用hashtable记录每个connected component，然后有了每个component的大小
之后用totalpairs计算最后的结果
void makeset(int x, unordered_map> &table)
{
table[x] = {x,1};
}
int findset(int x, unordered_map> &table)
{
auto &temp = table[x];
if (temp.first != x)
temp.first = findset(temp.first, table);
return temp.first;
}
void setunion(int x, int y, unordered_map> &table)
{
int repx = findset(x, table), repy = findset(y, table);
if (repx == repy)
return;
auto &pa = table[repx], &pb = table[repy];
if (pa.second >= pb.second) {
pb.first = pa.first;
pa.second += pb.second;
} else {
pa.first = pb.first;
pb.second += pa.second;
}
}
unordered_map> connected(const vector> &
pairs)
{
unordered_map> table;
for (const auto &p: pairs) {
if (table.find(p.first) == table.cend())
makeset(p.first, table);
if (table.find(p.second) == table.cend())
makeset(p.second, table);
setunion(p.first, p.second, table);
}
return table;
}
long totalpairs(unordered_map> &table, long n)
{
long partialsum {}, total {};
for (int i = 0; i != n; ++i)
if (table.find(i) != table.cend()) {
const auto &temp = table[i];
if (temp.first == i) {
total += partialsum * temp.second;
partialsum += temp.second;
}
}
long singles = n - partialsum;
total += singles * partialsum + singles * (singles-1)/2;
return total;
}
我的代码，不知道为什么所有的case都可以过，就是第１１个test case怎么都过不了
，不解啊不解 >_用的是union-find的数据结构，CLRS书上的算法
想法就是用hashtable记录每个connected component，然后有了每个component的大小
之后用totalpairs计算最后的结果
void makeset(int x, unordered_map
{
table[x] = {x,1};
}
int findset(int x, unordered_map
{
auto &temp = table[x];
if (temp.first != x)
temp.first = findset(temp.first, table);
return temp.first;
}
void setunion(int x, int y, unordered_map
{
int repx = findset(x, table), repy = findset(y, table);
if (repx == repy)
return;
auto &pa = table[repx], &pb = table[repy];
if (pa.second >= pb.second) {
pb.first = pa.first;
pa.second += pb.second;
} else {
pa.first = pb.first;
pb.second += pa.second;
}
}
unordered_map
pairs)
{
unordered_map
for (const auto &p: pairs) {
if (table.find(p.first) == table.cend())
makeset(p.first, table);
if (table.find(p.second) == table.cend())
makeset(p.second, table);
setunion(p.first, p.second, table);
}
return table;
}
long totalpairs(unordered_map
{
long partialsum {}, total {};
for (int i = 0; i != n; ++i)
if (table.find(i) != table.cend()) {
const auto &temp = table[i];
if (temp.first == i) {
total += partialsum * temp.second;
partialsum += temp.second;
}
}
long singles = n - partialsum;
total += singles * partialsum + singles * (singles-1)/2;
return total;
}
