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

链接：2316.统计无向图中无法互相到达点对数
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。请你返回 无法互相到达 的不同 点对数目 。

题解 1 - cpp

• 编辑时间：2023-10-21
• 执行用时：352ms
• 内存消耗：130.11MB
• 编程语言：cpp
• 解法介绍：并查集。

class UnionFind {
public:
    int n;
    vector<int> data, cnt;
    UnionFind(int n) : n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
        iota(data.begin(), data.end(), 0);
    }
    int size(int v) { return cnt[find(v)]; }
    int find(int v) {
        if (data[v] == v) return v;
        return data[v] = find(data[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) cnt[p1] += cnt[p2], data[p2] = p1;
    }
    bool same(int v1, int v2) { return find(v1) == find(v2); }
};
class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        UnionFind uf(n);
        for (auto &edge : edges) uf.uni(edge[0], edge[1]);
        long long res = 0;
        for (int i = 0; i < n; i++) {
            if (uf.data[i] != i) continue;
            res += (long long)uf.cnt[i] * (n - uf.cnt[i]);
        }
        return res / 2;
    }
};

题解 2 - python

• 编辑时间：2023-10-21
• 执行用时：408ms
• 内存消耗：61.26MB
• 编程语言：python
• 解法介绍：同上。

class UnionFind:
    def __init__(self, n) -> None:
        self.n = n
        self.data = [i for i in range(0, n)]
        self.cnt = [1] * n
    def size(self, v: int) -> int:
        return self.cnt[self.find(v)]
    def find(self, v: int) -> int:
        if self.data[v] != v:
            self.data[v] = self.find(self.data[v])
        return self.data[v]
    def uni(self, v1: int, v2: int):
        p1 = self.find(v1)
        p2 = self.find(v2)
        if p1 != p2:
            self.cnt[p1] += self.cnt[p2]
            self.data[p2] = p1
    def same(self, v1: int, v2: int):
        return self.find(v1) == self.find(v2)
class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for [n1, n2] in edges:
            uf.uni(n1, n2)
        return sum(uf.cnt[i] * (n - uf.cnt[i]) if uf.data[i] == i else 0 for i in range(n)) // 2

题解 3 - rust

• 编辑时间：2023-10-21
• 执行用时：36ms
• 内存消耗：14.85MB
• 编程语言：rust
• 解法介绍：同上。

pub struct UnionFind {
    pub n: usize,
    pub data: Vec<usize>,
    pub cnt: Vec<usize>,
}
impl UnionFind {
    pub fn new(n: usize) -> Self {
        let mut data = vec![0; n];
        for i in 0..data.len() {
            data[i] = i;
        }
        Self {
            n,
            data,
            cnt: vec![1; n],
        }
    }
    pub fn size(&mut self, v: usize) -> usize {
        let idx = self.find(v);
        self.cnt[idx]
    }
    pub fn find(&mut self, v: usize) -> usize {
        if self.data[v] != v {
            self.data[v] = self.find(self.data[v]);
        }
        self.data[v]
    }
    pub fn uni(&mut self, v1: usize, v2: usize) {
        let p1 = self.find(v1);
        let p2 = self.find(v2);
        if p1 != p2 {
            self.cnt[p1] += self.cnt[p2];
            self.data[p2] = p1;
        }
    }
    pub fn same(&mut self, v1: usize, v2: usize) -> bool {
        self.find(v1) == self.find(v2)
    }
}
impl Solution {
    pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
        let n = n as usize;
        let mut uf = UnionFind::new(n);
        for edge in edges {
            uf.uni(edge[0] as usize, edge[1] as usize);
        }
        (0..n)
            .map(|i| {
                if uf.data[i] != i {
                    0
                } else {
                    uf.cnt[i] * (n - uf.cnt[i])
                }
            })
            .sum::<usize>() as i64
            / 2
    }
}