做ppt图片用的网站有哪些,1688免费货源,wordpress心理教育网站,手机app推广联盟打卡记录 统计无向图中无法互相到达点对数#xff08;并查集 / DFS#xff09;
链接
并查集 思路#xff1a;用并查集将连通区域的连在一起#xff0c;再遍历所有点#xff0c;用hash表存储不同连通块的元素个数#xff0c;然后 乘积和 便是答案。 注意#xff1a;
/…打卡记录 统计无向图中无法互相到达点对数并查集 / DFS
链接
并查集 思路用并查集将连通区域的连在一起再遍历所有点用hash表存储不同连通块的元素个数然后 乘积和 便是答案。 注意
// 计算乘积和妙
long long ans 0, total 0;
for (auto [_, x] : hash) {ans x * total;total x;
}class Solution {
public:long long countPairs(int n, vectorvectorint edges) {vectorint p(n);for (int i 0; i n; i) p[i] i;functionint(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_mapint, 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;}
};DFS 思路搜寻每个连通块的元素个数之后同理便可以计算出答案。 class Solution {
public:long long countPairs(int n, vectorvectorint edges) {vectorint g[n];for (auto edge : edges) {int a edge[0], b edge[1];g[a].push_back(b);g[b].push_back(a);}vectorbool st(n, false);functionint(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;}
};反转二叉树的奇数层BFS[层序遍历] / DFS
链接
BFS层序遍历 思路在层序遍历使用 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) {queueTreeNode* q;q.push(root);bool flag false;while (!q.empty()) {vectorTreeNode* 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;}
};
