Leetcode每日一题 —— 2685. 统计完全连通分量的数量

对于一个完全连通分量，设 E 为边数，V 为点数，则 E = V \times (V - 1) \div 2。

class Solution {

public:

    int countCompleteComponents(int n, vector<vector<int>>& edges) {

        vector<int> vis(n);

        int ans = 0;

        vector<vector<int>> adj(n);

        for (auto &e : edges) {

            int u = e[0], v = e[1];

            adj[u].push_back(v);

            adj[v].push_back(u);

        }

        auto bfs = [&](int s) -> bool {

            queue<int> q;

            q.push(s);

            int e = 0, cnt = 0;

            while (!q.empty()) {

                int x = q.front();

                q.pop();

                if (vis[x]) continue;

                cnt++;

                vis[x] = 1;

                for (int y : adj[x]) {

                    if (vis[y]) continue;

                    e++;

                    q.push(y);

                }

            }

            return e == cnt * (cnt - 1) / 2;

        };

        for (int i = 0; i < n; i++) {

            if (!vis[i]) {

                ans += bfs(i);

            }

        }

        return ans;

    }

};

并查集。

class Solution {

public:

    int countCompleteComponents(int n, vector<vector<int>>& edges) {

        vector<int> p(n,0);

        vector<pair<int,int>> cnt(n,pair<int,int>(1,0));

        vector<bool> st(n,0);

        iota(p.begin(),p.end(),0);

        int res = 0;

        auto find = [&p](this auto&& find, int x) -> int {

            return x == p[x] ? x : p[x] = find(p[x]);

        };

        

        for(const auto& e : edges) {

            int u = e[0], v = e[1];

            int pu = find(u), pv = find(v);

            if(pu != pv) {

                p[pu] = pv;

                cnt[pv].second += cnt[pu].second;

                cnt[pv].first += cnt[pu].first;

            }

            cnt[pv].second += 1;

        }

        

        for(int i = 0; i < n; i++) {

            int p = find(i);

            if(!st[p]) {

                st[p] = true;

                res += (cnt[p].second * 2 == (cnt[p].first - 1) * cnt[p].first);

            }

        }

        return res;

    }

};

并查集额外对边数进行追踪即可。

class Solution {

public:

    int countCompleteComponents(int n, vector<vector<int>>& edges) {

        // 要判定连通分量内是不是每对节点间都一条边

        // 需要对连通分量中的边计数，n 个顶点要有 n(n-1)/2 条边

        // 题目保证不存在重复的边，用并查集合并的时候我们可以顺带记录边数量

        vector<int> parents(n,-1);

        vector<int> sizes(n,1);

        vector<int> sides(n,0);

        auto find=[&](auto&& self,int x)->int{

            return parents[x]==-1 ? x : parents[x]=self(self,parents[x]);

        };

        auto merge=[&](int x1,int x2)->void{

            int root1=find(find,x1),root2=find(find,x2);

            if(root1==root2){

                // 就算二者已经合并，也要累加边数

                sides[root1]++;

                return;

            }

            if(sizes[root1]<sizes[root2]){

                // 保证是小树并入大树

                swap(root1,root2);

            }

            parents[root2]=root1;

            sizes[root1]+=sizes[root2];

            sides[root1]+=sides[root2]+1;

        };

        for(vector<int>& e:edges){

            merge(e[0],e[1]);

        }

        // 扫描来进行判断

        int res=0;

        for(int i=0;i<n;i++){

            if(parents[i]==-1){

                // 找到一个连通分量的代表节点

                int numV=sizes[i]; // 顶点数

                int numS=sides[i]; // 边数

                if(((numV*(numV-1))>>1)==numS){

                    res++;

                }

            }

        }

        return res;

    }

};

Kotlin实现（并查集，构建时维护根的边数和点数）：

class Solution {

    fun countCompleteComponents(n: Int, edges: Array<IntArray>): Int {

        val fa = IntArray(n) { it }

        val edgeCount = IntArray(n) { 0 }

        val pointCount = IntArray(n) { 1 }

        fun findRoot(x: Int): Int {

            if (x != fa[x]) {

                fa[x] = findRoot(fa[x])

            }

            return fa[x]

        }

        for ((a, b) in edges) {

            val aRoot = findRoot(a)

            val bRoot = findRoot(b)

            if (aRoot == bRoot) {

                edgeCount[bRoot]++

            } else {

                fa[aRoot] = bRoot

                pointCount[bRoot] += pointCount[aRoot]

                edgeCount[bRoot] += (edgeCount[aRoot] + 1)

            }

        }



        var ans = 0

        for (root in fa.indices) {

            if (root != fa[root]) {

                continue

            }

            val e = edgeCount[root]

            val p = pointCount[root]

            if (p * (p - 1) == e * 2) {

                ans++

            }

        }

        return ans

    }

}