提供邯郸手机网站建设,网站数据库如何导入,百度指数查询官网大数据,抖音引流推广免费软件app1. 题意
给定一个无向图#xff0c; 统计无法互相到达的点对数。 统计无法互相到达点对数
2. 题解
其实还是求联通块#xff0c;求联通块可以使用搜索进行标记。还要求得联通块中元素的大小。
联通块其实也就是不相交集合#xff0c;也可以用并查集来做。
每求得一个联…1. 题意
给定一个无向图 统计无法互相到达的点对数。 统计无法互相到达点对数
2. 题解
其实还是求联通块求联通块可以使用搜索进行标记。还要求得联通块中元素的大小。
联通块其实也就是不相交集合也可以用并查集来做。
每求得一个联通块的元素个数与之前所有联通块元素个数相乘
所以本题目两种做法
搜索 前缀和并查集 前缀和
2.1 并查集
并查集的介绍
不记录元素个数的
class Solution {public:
class UnionFind {public:explicit UnionFind(int sz):cnt(sz),pa(sz){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k pa[k] ? k : pa[k] Find(pa[k]);}void Union(int k1, int k2 ){int p0 Find(k1);int p1 Find(k2);if ( p0 ! p1) {pa[p0] p1;cnt--;}}int Cnt(){return cnt;}private:vectorint pa;int cnt;
};long long countPairs(int n, vectorvectorint edges) {UnionFind uf(n);int sz edges.size();for (int i 0; i sz; i)uf.Union(edges[i][0], edges[i][1]);unordered_mapint, int um;for (int i 0; i n; i ) {um[uf.Find(i)];}vectorint node;for (auto [k, v]: um) {node.push_back(v);}long long ans 0;int pre 0;for (int i 0; i node.size(); i)ans 1L * pre * node[i], pre node[i]; cout ans endl;return ans;}
};记录元素个数的
class Solution {public:
class UnionFind {public:explicit UnionFind(int _sz):cnt(_sz),pa(_sz),sz(_sz, 1){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k pa[k] ? k : pa[k] Find(pa[k]);}void Union(int k1, int k2 ){int p0 Find(k1);int p1 Find(k2);if (p0 p1)return ;if (sz[p0] sz[p1] ) {pa[p0] p1;sz[p1] sz[p0];}else {pa[p1] p0;sz[p0] sz[p1];}}int Cnt(){return cnt;}int Size(int idx){ return sz[idx]; }private:vectorint pa,sz;int cnt;
};long long countPairs(int n, vectorvectorint edges) {UnionFind uf(n);int sz edges.size();for (int i 0; i sz; i)uf.Union(edges[i][0], edges[i][1]);vectorint node;for (int i 0; i n; i) {if (uf.Find(i) i)node.push_back(uf.Size(i));}long long ans 0;int pre 0;for (int i 0; i node.size(); i)ans 1L * pre * node[i], pre node[i]; return ans;}
};2.2 搜索
DFS
class Solution {public:void dfs( int i, int num, vectorvectorint g, vectorbool vis) {num;vis[i] true;for (int v: g[i]) {if (!vis[v]) {dfs(v, num, g, vis);}}}long long countPairs(int n, vectorvectorint edges) {vectorvectorint g(n, vectorint());vectorbool vis(n, false);for (auto v:edges){int f v[0];int t v[1];g[f].push_back(t);g[t].push_back(f);}long long ans 0;long long pre 0;for (int i 0; i n; i ) {if (!vis[i]) {int num 0;dfs( i, num, g, vis);ans 1l * pre * num;pre num; }}return ans;}
};BFS
class Solution {public:void bfs( int i, int num, vectorvectorint g, vectorbool vis) {queueint nq;nq.push(i);num;vis[i] true;while( !nq.empty() ) {int idx nq.front();nq.pop();for (auto v:g[idx]) {if (!vis[v]) {nq.push(v);num;vis[v] true;}}}}long long countPairs(int n, vectorvectorint edges) {vectorvectorint g(n, vectorint());vectorbool vis(n, false);for (auto v:edges){int f v[0];int t v[1];g[f].push_back(t);g[t].push_back(f);}long long ans 0;long long pre 0;for (int i 0; i n; i ) {if (!vis[i]) {int num 0;bfs( i, num, g, vis);cout num endl;ans 1l * pre * num;pre num; }}return ans;}
};
