2316.Count Unreachable Pairs of Nodes in an Undirected Graph

題目

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[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]].
Therefore, we return 14.

Constraints:

• 1 <= n <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• There are no repeated edges.

思路

如果2個node没有法通往對方,代表他們在不同的tree上,如果我們能找出總共有幾棵樹、每棵樹上面有幾個node就能藉此計算出unreachable 的node pair。這時,我們可以用union find來將所有的node分類進不同的tree中。

Union find

維基百科給出的定義如下

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.

Union find提供了3個method: add find merge

• add 是將一個node加入到一個set(tree)中
• find 會從一個node開始，往上找parent，直到找出一個set中的representative member或是tree的root
• merge 則是試圖將兩個disjoint的set合併

union find 還有更進階的版本是可以依照每個node的rank去找root，但由於本題只需要知道有幾個disjoint set所以不需要實作這個部分。

首先我們建立一個Array來maintain每個node所在的樹的root，一開始假設所有的node都是disjoint的樹，所以大家的root都是自己

const parent:number[] = new Array(n).fill(0).map(((_,i) => i));

以example 1為例，現在parent中的值如下：

node	0	1	2
parent	0	1	2

接下來我們要實作union find的3個method。首先，add是將node加入倒tree中，由於我們在這裡沒有要實際建立tree，所以不需要實做這個function，而find的function如下：

function find(parent: number[], node: number):number {
    if(parent[node] === node) return node

    // path compression
    parent[node] = find(parent, parent[node])
    return parent[node];
}

這個function會接收前面的parent array與要找parent的node作為input，並return該node所在的tree root的編號。其中path compression的部分，則是當這個node不是這顆tree中的root時，要一 層一層的往上找到root，以確保我們在parent array中所存的node都是該棵樹的root id，同時也可以將路徑上經過的parent node都更新其parent直到最新的root。

接著時做unionfunction：

function union(parent: number[], u: number, v: number): void {
    const parentU = find(parent, u);
    const parentV = find(parent, v);

    if (parentU !== parentV) parent[parentV] = parentU;
}

這個function會接收parent array與2個node作為input，並利用前面的findfunction 檢查這兩個node是否有同一個root，若是，則將兩棵樹併起來，實際的操作為：將其中一棵樹的root(parentV)的parent更新為另一棵樹的root(parentU)。

這邊就可以看到前面path compression的作用體現出來了，如果在find的時候沒有做path compression，有可能明明兩個node是在同一棵樹底下，但拿到的卻是路徑中的parent而非root，以至於第5行的判斷式不通過，而沒有更新。

最後，利用merge function對於每一個edge的node pair做一次merge，將相連的node倆倆合併，最後再檢查總共有幾個root就可以知道有幾棵disjoint tree

function countPairs(n: number, edges: number[][]): number {
    const parent:number[] = new Array(n).fill(0).map(((_,i) => i));

    edges.forEach(([u, v]) => {
        union(parent, u, v);
    });

    for(let i = 0; i < n; i ++) {
        find(parent, i);
    }
    
    const sizes = Object.values(parent.reduce<Record<number, number>>((map, p) => {
        map[p] = map[p] ? map[p] + 1 : 1;
        return map;
    }, {}));
    
    return sizes.reduce<number>((acc, curr) => (acc + curr * (n - curr)), 0) / 2;
};

注意在做完所有的merge之後，要再對每一個node做一次find，利用function中的path compression來確保parent array中所有的值都是該棵樹中的root。

最後loop through parent array統計出每棵樹有幾個node，存於size這個變數中，對於每一棵樹，unreachable node pair的數量就是自己的node數 * 不在該棵樹上的node數，最後由於會重複計算，所以結果再除以2即可。