【算法题】统计无向图中无法互相到达点对数
  FTGOknwdYkLB 2023年11月02日 66 0


题目:

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

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

示例 1:

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

输入:n = 3, edges = [[0,1],[0,2],[1,2]]

输出:0

解释:所有点都能互相到达,意味着没有点对无法互相到达,所以我们返回 0 。

示例 2:

【算法题】统计无向图中无法互相到达点对数_算法_02

输入:n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出:14
解释:总共有 14 个点对互相无法到达:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示:

1 <= n <= 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。

java代码:

class Solution {
    List<Integer>[] g;
    boolean[] vis;
    int cnt;

    public long countPairs(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        vis = new boolean[n];
        var ans = 0L;
        for (int i = 0, tot = 0; i < n; ++i)
            if (!vis[i]) {
                cnt = 0;
                dfs(i);
                ans += (long) cnt * tot;
                tot += cnt;
            }
        return ans;
    }

    void dfs(int x) {
        vis[x] = true;
        ++cnt;
        for (var y : g[x]) if (!vis[y]) dfs(y);
    }
}


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
FTGOknwdYkLB