どういうアプローチを行なったか

全てのノードを繋ごうと考えると、ネットワークから孤立しているノードの数が答えだと考えた。
ゼロから繋がらないノードが一つあればネットワークを一つだけ付け替えればいいと考えた。これだと以下のパターンがダメってことはあとで気づいた。

このパターンでは僕の解法では二つ付け替えなければならないが、このパターンでは一つで良い。
でゼロから切断されたTreeの数を数えればよかったのだと気づいたが時すでに遅しだった。

じゃあどうするべきだったか

解法

まずconnectionsの数がノードの数をNとすると connections < N - 1の場合は答えは必ず-1となる。
分断されたネットワークをグラフと定義すると最低必要な線はグラフをG個と定義すればG - 1 個の線が必要である。なのでグラフの個数を数え上げてしまえばこの問題は終了となる。
少し具体的に考えてみると、以下のようにグラフの数が一つ（つまり全て繋がってる状態だと）0個の線が必要。

グラフの数が二つであれば、0123のどれかから45に向けて一つ線が引かれたらそれで全てのノードがつながることになる

やはりG - 1 を答えとするので大丈夫そうである。

さて僕の考え方もこれに近いところだったのだが、グラフの個数を数え上げるというところの実装に困ってしまった。（もちろん時間切れもあったが）

ここでは二つの実装方法がある。

DFS

どんなデータ構造でDFSを行うかというと、配列とSetを使用する。
まずノード個数分の配列を用意してその一つ一つにSetを用意する。
イメージとしてはこんな感じ

各項目ごとにsetの中身を探索していき、すでに探索済みの項目があった場合はカウントは０として新たに出た数字のみが出てきた項目は１をカウントするようにすると、全てのグラフを合計できる。

赤は初めて到達したということ灰色はすでに到達済みを表している。灰色のノードがあると確実にどこかのグラフに属しているということなのでそれ以降の探索をする必要がなくなる。
各項目についてDFSを行うので最初の0のノードを探索すると１までつながる、あとは各項目について調べていくとすでに繋がっているノードは必ず到着済みとなるのでグラフカウントはされなくなる。

こうすることで解決できる。

サンプルコード

var makeConnected = function(n, connections) {
    if(connections.length < n - 1) {
        return -1
    }

    const group = Array.from({length: n}).map(() => new Set())
    for(const [i, j] of connections){
        group[i].add(j)
        group[j].add(i)
    }

    const seen = Array.from({length: n}).fill(0)

    function dfs(i) {
        if(seen[i]) {
            return 0
        }

        seen[i] = 1
        for(const j of group[i]) {
            dfs(j)
        }

        return 1
    }
    const graphCount = Array.from({length: n}).reduce((a,b,i) => a + dfs(i), 0)

    return graphCount - 1
}

素集合連結リスト

名前の通りだがグラフ毎に連結リストを作成する方法である。
連結リストの一番rootのみを各リストに保存していく。さて与えられてるconnectionsを [[0,1],[0,2],[1,3],[0,3],[4,5]]とすると本来の変換は上だが、変換をまとめることにより下のように変換できる。

これはconnectionsの順番によっても変化するが、変更をまとめることで変化がなくなるところが必ず生まれる。そこがグラフのルートになる。そのため素集合連結リストで処理していき、各配列の項目と添字を比較するとグラフが何個含まれているかを数えることができる。

Example

var makeConnected = function(n, connections) {
    if(connections.length < n - 1) {
        return -1
    }

    const parent = Array.from({length: n}).map((a, i) => i)
    let countComponents = 0;

    for(const [i, j] of connections) {
        const p1 = findParent(parent, i);
        const p2 = findParent(parent, j);
        if(p1 != p2) {
            parent[p1] = p2;
        }
    }
    console.log(parent)
    for(let i = 0; i < n; i++){
        if(parent[i] == i) {
            countComponents++;
        }
    }   

    return countComponents - 1 
}

function findParent(par, i) {
    while(i != par[i]) {
        i = par[i]
    }
    return i
}

DFSの方は結構直感的だったのでできても良い気がした。
解法2は要復習だなぁ

Leetcode 問題1319を解く

どういうアプローチを行なったか

解法

DFS

素集合連結リスト