人森很精彩，所以要把所有事情都記起來=ˇ=

好像很久沒寫leetcode了

寫題算... 基本款的吧，雖然我也搞了滿久的= =

有些東西久久不用就會忘啊~

這題基本上就是要找出多餘的連線，並且算出是否能用多餘的連線把剩下的電腦連起來

如果沒辦法就回傳-1，不然就回傳新增的連線數量

一看就知道是跟union有關的題目...

講道理只要先把所有的連線都連起來，過程中同時去計算那個連線是否為多餘的連線

最後算出需要多少連線才能把玫璉到的電腦連起來，比較一下多餘的連線數量和需要的連線的數量

就可以得到結果了

只是具體要怎麼做呢﹑大概就分成兩步吧：

首先是把所有的連線都連起來，過程中同時去計算那個連線是否為多餘的連線

一開始可能會想用map之類的東西，但其實不用這麼麻煩

只要用union的概念來看就行了，就是... 分群的概念吧

在每一個電腦上貼上一個標籤，標出他們是哪一組的，藉此來達到分群的目的

所以一開始可以用一個陣列來表示標籤，初始時大家都是屬於自己那一群的：

vector<int> connectedGroup;
for (int i = 0; i < n; ++i)
    {
        connectedGroup.emplace_back(i);
    }

接下來就可以開始連線了，首先我們要先知道怎麼判對兩個電腦是不是同一群的

所以我們可以先寫一個function來找出那個電腦是哪一群的：

int findGroup(vector<int>& connectedGroup, int i)
    {
        if(connectedGroup[i] != i) 
        {
            connectedGroup[i] = findGroup(connectedGroup, connectedGroup[i]);
        }
        
        return connectedGroup[i];
    }

這邊用遞迴的概念，在找的時候順便對這些電腦做標籤，這算是一個我覺得滿重要的技巧，這樣做才會每次找的時候去更新標籤內容

接著可以開始找多餘的連線了，大概的code是這樣：

int extraEdge = 0;
    for (vector<int>& conn : connections)
        {
            int g1 = findGroup(connectedGroup, conn[0]);
            int g2 = findGroup(connectedGroup, conn[1]);
            
            if(g1 == g2) 
                extraEdge++;
            else 
                connectedGroup[g1] = g2;   
        }

當g1 == g2時，其實就表示兩個是同一個group，這個連線是一個多餘的連線

否則就更新connectedGroup，把兩個group標成同一個group

這邊說一下更新哪一個其實是沒有區別的，因為下次findGroup的時候就會再去更新成同一個標籤，所以對於最後的結果也不會有影響

再來第二步就是算出有幾個group，概念非常簡單

我們只要看connectedGroup裡面有哪些電腦的標籤和初始化時一樣，就表示有幾個group了：

int groupSize = 0;
    for (int i = 0; i < n; ++i)
        {
            if (connectedGroup[i] == i)
                groupSize++;
        }

最後就可以得到答案：

return extraEdge >= groupSize - 1 ? groupSize - 1 : -1;

那這題就空虛的結束了

比較難懂的應該是第一part那邊吧，我都是卡那邊XD

不過對於union熟悉的人來說那應該是很基本的概念，要好好記得啊~

那就下題再見了~