【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集

简介: 【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集

统计无向图中无法互相到达点对数【LC2316】

给你一个整数 n ,表示一张 无向图 中有 n 个节点,编号为 0n - 1 。同时给你一个二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示节点 aibi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目

思路

  • **并查集查找连通性:**记录每个点的父节点,父节点相同的节点可以相互到达;与父节点不同的节点,不可以互相到达
  • 计算数量,父节点为i的节点数量为a,那么这个节点与n − a个节点不相邻,统计数量
  • 统计结果,由于重复计算,最终结果需要除以2

实现

class Solution {
    public long countPairs(int n, int[][] edges) {
        // 并查集记录每个点的父节点,父节点相同的节点可以相互到达;与父节点不同的节点,不可以互相到达
        // 计算数量,父节点为i的节点数量为a,那么这个节点与n-a个节点不相邻,统计数量
        // 统计结果,由于重复计算,最终结果需要除以2
        UnionFind union = new UnionFind(n);
        for (int[] edge : edges){
            union.union(edge[0], edge[1]);
        }
        long res = 0L;
        for (int i = 0; i < n; i++){
            res += n - union.getSize(i);
        }
        return res / 2;
    }
}
// 并查集类
class UnionFind {
    private int[] p;// 父节点
    private int[] size;// 每个节点的子节点个数(包括自身)
  // 初始化
    public UnionFind(int n) {
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            size[i] = 1;
        }
    }
  // 找到节点x的根
    public int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
  // 在并查集中加入a->b的根
    public void union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            if (size[pa] > size[pb]) {
                p[pb] = pa;
                size[pa] += size[pb];
            } else {
                p[pa] = pb;
                size[pb] += size[pa];
            }
        }
    }
    public int getSize(int a){
        int father = find(a);
        return size[father];
    }
}

复杂度分析

时间复杂度:O ( n + α ( m ) ∗ m ) ,n为图中顶点的数目,m为图中边的数目。其中 α为阿克曼函数的反函数,其增长极其缓慢,也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

空间复杂度:O ( n ) ,空间复杂度主要取决于并查集,并查集需要 O ( n )的空间,因此总的空间复杂度为O ( n )

目录
相关文章
|
7月前
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
【每日一题Day302】LC849到最近的人的最大距离 | 贪心+分类讨论
55 0
|
7月前
【每日一题Day342】LC2578最小和分割 | 贪心
【每日一题Day342】LC2578最小和分割 | 贪心
48 0
|
7月前
|
人工智能 BI
【每日一题Day267】LC834树中距离之和 | 换根dp
【每日一题Day267】LC834树中距离之和 | 换根dp
46 0
|
7月前
|
算法 测试技术 C#
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
|
7月前
|
vr&ar
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
72 1
|
7月前
【每日一题Day170】LC1040移动石子直到连续 II | 双指针 贪心 数学
【每日一题Day170】LC1040移动石子直到连续 II | 双指针 贪心 数学
53 1
|
7月前
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
【每日一题Day223】LC1130叶值的最小代价生成树 | 贪心 区间dp
47 0
|
7月前
|
人工智能 BI
【每日一题Day333】LC2603收集树中金币 | 拓扑排序
【每日一题Day333】LC2603收集树中金币 | 拓扑排序
49 0
|
7月前
【每日一题Day265】LC979在二叉树中分配硬币 | 树形dp
【每日一题Day265】LC979在二叉树中分配硬币 | 树形dp
56 0
|
7月前
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
58 0