leetcode_2316 统计无向图中无法互相到达点对数

1. 题意

给定一个无向图， 统计无法互相到达的点对数。
统计无法互相到达点对数

2. 题解

其实还是求联通块，求联通块可以使用搜索进行标记。还要求得联通块中元素的大小。

联通块其实也就是不相交集合，也可以用并查集来做。

每求得一个联通块的元素个数，与之前所有联通块元素个数相乘；

所以本题目两种做法：

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:vector<int> pa;int cnt;
};long long countPairs(int n, vector<vector<int>>& edges) {UnionFind uf(n);int sz = edges.size();for (int i = 0; i < sz; ++i)uf.Union(edges[i][0], edges[i][1]);unordered_map<int, int> um;for (int i = 0; i < n; ++i ) {um[uf.Find(i)]++;}vector<int> 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:vector<int> pa,sz;int cnt;
};long long countPairs(int n, vector<vector<int>>& edges) {UnionFind uf(n);int sz = edges.size();for (int i = 0; i < sz; ++i)uf.Union(edges[i][0], edges[i][1]);vector<int> 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, vector<vector<int>> &g, vector<bool> &vis) {++num;vis[i] = true;for (int &v: g[i]) {if (!vis[v]) {dfs(v, num, g, vis);}}}long long countPairs(int n, vector<vector<int>>& edges) {vector<vector<int>> g(n, vector<int>());vector<bool> 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, vector<vector<int>> &g, vector<bool> &vis) {queue<int> 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, vector<vector<int>>& edges) {vector<vector<int>> g(n, vector<int>());vector<bool> 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;}
};