思路:用并查集将连通区域的连在一起,再遍历所有点,用hash表存储不同连通块的元素个数,然后 乘积和 便是答案。
注意:
// 计算乘积和(妙)
long long ans = 0, total = 0;
for (auto [_, x] : hash) {
ans += x * total;
total += x;
}
class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
vector<int> p(n);
for (int i = 0; i < n; ++i) p[i] = i;
function<int(int)> find = [&](int u) -> int {
if (p[u] != u) p[u] = find(p[u]);
return p[u];
};
for (auto& edge : edges) {
int x = find(edge[0]), y = find(edge[1]);
if (x != y) p[x] = y;
}
unordered_map<int, int> hash;
for (int i = 0; i < n; ++i) {
hash[find(i)]++;
}
long long ans = 0, total = 0;
for (auto [_, x] : hash) {
ans += x * total;
total += x;
}
return ans;
}
};
思路:搜寻每个连通块的元素个数,之后同理便可以计算出答案。
class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
vector<int> g[n];
for (auto& edge : edges) {
int a = edge[0], b = edge[1];
g[a].push_back(b);
g[b].push_back(a);
}
vector<bool> st(n, false);
function<int(int)> dfs = [&](int u) -> int {
if (st[u]) return 0;
int cnt = 1;
st[u] = true;
for (auto& e : g[u]) cnt += dfs(e);
return cnt;
};
long long ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
int cnt = dfs(i);
ans += sum * cnt;
sum += cnt;
}
return ans;
}
};
思路:在层序遍历使用 queue 的基础上,将奇数层的整层的节点按照从左到右的顺序全部存入新开的一个数组中,然后对数组中的所有值进行颠倒。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* reverseOddLevels(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
bool flag = false;
while (!q.empty()) {
vector<TreeNode*> t;
while (!q.empty()) {
t.push_back(q.front());
q.pop();
}
if (flag) {
for (int i = 0, j = t.size() - 1; i < j; ++i, --j)
swap(t[i]->val, t[j]->val);
}
flag = !flag;
for (auto u : t) {
if (u->left) q.push(u->left);
if (u->right) q.push(u->right);
}
}
return root;
}
};