主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)整數(shù) n 代表著現(xiàn)在有 n 個(gè)人且編號(hào)為 0 到 n - 1。你同時(shí)也被給定一個(gè)索引值從 0 開始數(shù)的二維整數(shù)陣列 meetings，其中 meetings[i] = [xi, yi, timei] 代表著編號(hào) xi 和編號(hào) yi 的人在時(shí)間點(diǎn) timei 時(shí)有會(huì)議。而同一個(gè)人可能會(huì)同時(shí)參加多個(gè)會(huì)議。最終，你還會(huì)被給定一個(gè)整數(shù) firstPerson。
編號(hào) 0 的人有一個(gè)祕(mì)密，而他在一開始時(shí)間 0 的時(shí)候告訴祕(mì)密給編號(hào) firstPerson 的人。而這個(gè)祕(mì)密將會(huì)在每次知道祕(mì)密的人參加會(huì)議時(shí)分享給其他人。更正式地說，對(duì)於每場(chǎng)會(huì)議，如果編號(hào) xi 的人在時(shí)間點(diǎn) timei 前知道祕(mì)密，則他會(huì)在會(huì)議中分享祕(mì)密給編號(hào) yi 的人；反之亦然。
祕(mì)密的分享是立即性的。也就是說，某個(gè)人可以在知曉祕(mì)密的同一瞬間將該祕(mì)密分享給他同時(shí)參加的其他會(huì)議上的人。
回傳一個(gè)由在所有會(huì)議結(jié)束之後，知道祕(mì)密的所有人所組成的列表。你可以按任意順序回傳答案。
限制：
2 ≦ n ≦ 10 ^ 5
1 ≦ meetings.length ≦ 10 ^ 5
meetings[i].length == 3
0 ≦ xi, yi ≦ n - 1
xi != yi
1 ≦ timei ≦ 10 ^ 5
1 ≦ firstPerson ≦ n - 1
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
輸出： [0,1,2,3,5]
解釋：
在時(shí)間點(diǎn) 0，編號(hào) 0 的人與編號(hào) 1 的人分享祕(mì)密。
在時(shí)間點(diǎn) 5，編號(hào) 1 的人與編號(hào) 2 的人分享祕(mì)密。
在時(shí)間點(diǎn) 8，編號(hào) 2 的人與編號(hào) 3 的人分享祕(mì)密。
在時(shí)間點(diǎn) 10，編號(hào) 1 的人與編號(hào) 5 的人分享祕(mì)密。
因此，編號(hào) 0 、 1 、 2 、 3 和 5 的人在所有會(huì)議結(jié)束後是知道祕(mì)密的。
範(fàn)例 2：
輸入： n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
輸出： [0,1,3]
解釋：
在時(shí)間點(diǎn) 0，編號(hào) 0 的人與編號(hào) 3 的人分享祕(mì)密。
在時(shí)間點(diǎn) 2，編號(hào) 1 和 2 的兩個(gè)人都不知道祕(mì)密。
在時(shí)間點(diǎn) 3，編號(hào) 3 的人與編號(hào) 0 和 1 的人分享祕(mì)密。
因此，編號(hào) 0 、 1 和 3 的人在所有會(huì)議結(jié)束後是知道祕(mì)密的。
範(fàn)例 3：
輸入： n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
輸出： [0,1,2,3,4]
解釋：
在時(shí)間點(diǎn) 0，編號(hào) 0 的人與編號(hào) 1 的人分享祕(mì)密。
在時(shí)間點(diǎn) 1，編號(hào) 1 的人與編號(hào) 2 的人分享祕(mì)密，而編號(hào) 2 的人再分享祕(mì)密給編號(hào) 3 的人。
注意到編號(hào) 2 的人可以在知道祕(mì)密的同時(shí)分享給其他人。
在時(shí)間點(diǎn) 2，編號(hào) 3 的人與編號(hào) 4 的人分享祕(mì)密。
因此，編號(hào) 0 、 1 、 2 、 3 和 4 的人在所有會(huì)議結(jié)束後是知道祕(mì)密的。
解題思維：
首先我們把所有會(huì)議按照開始的時(shí)間點(diǎn)由小排到大，並將相同時(shí)間點(diǎn)的會(huì)議放在一起看（可以全部丟到一個(gè)陣列中等。注意，這邊是把會(huì)議聚在一起，不是人本身聚在一起。）
假設(shè)現(xiàn)在時(shí)間點(diǎn)是 T，而且有 m1 、 m2 、 …… 、 mk 這些會(huì)議要進(jìn)行，其中 mi = [xi, yi] 代表著 xi 和 yi 在這個(gè)時(shí)間點(diǎn) T 有會(huì)議。
為了「即時(shí)」分享祕(mì)密，我們需要知道哪些人是一組的。因此我們需要掃過每一個(gè)會(huì)議 mi，來把 xi 、 yi 分在同一組（先不論實(shí)際上要怎麼實(shí)作）。
例如說我們可能有 [0, 1] 、 [1, 2] 和 [5, 6] 這三場(chǎng)會(huì)議。則掃完會(huì)議之後，我們應(yīng)當(dāng)要知道 [0, 1, 2] 是一組的，而 [5, 6] 是另一組。可以看到這就是為何前面提到不能直接把人聚在一起，因?yàn)闀?huì)議時(shí)間點(diǎn)一樣不代表在這邊會(huì)是同一組。
而此時(shí)我們便可以讓同一組的人彼此分享祕(mì)密（如果有人知道的話）。再次提醒這組的祕(mì)密分享是與其他組獨(dú)立的。
因?yàn)檫@個(gè)分組只在這個(gè)時(shí)間點(diǎn)有意義而已，因此分享完之後就要各自分散了。由小到大判斷完所有時(shí)間點(diǎn)各自的會(huì)議之後，再掃過一次所有人看哪些人知道祕(mì)密。把他們丟進(jìn)一個(gè)陣列中即是所求。
接著來談實(shí)作，可以看到「組」的概念即是「集合」。「分在同一組」可以看作是集合之間的「合併」。因此我們可以使用併查集（Union-Find Set，參見這題的介紹）來實(shí)作。注意在將兩個(gè)集合合併時(shí)，如果此時(shí)兩個(gè)集合中的「代表」（Representative）有某一個(gè)知道祕(mì)密則合併之後的集合之代表也需要「繼承」這個(gè)祕(mì)密，方便後面分享祕(mì)密的時(shí)候可以直接參考集合代表知不知道祕(mì)密。
分完組之後，再掃過這期間有參加過會(huì)議的人（其實(shí)就是再掃過一次 m1 、 m2 、 …… 、 mk）來判斷各自會(huì)不會(huì)被分享到祕(mì)密（如上所述，參見同一集合中的代表即可）。
分享完祕(mì)密後，需要再把組別各自拆開。也就是說，要將集合重設(shè)到原本各自獨(dú)立一個(gè)的狀態(tài)。一樣，這邊可以再掃過一次所有會(huì)議來看哪些人有參加會(huì)議。把他們的集合資訊重設(shè)即可。
其餘部份是一樣的。
最後是時(shí)間複雜度分析：
可以看到單一一個(gè)時(shí)間點(diǎn) T 所需時(shí)間為 O(k × α(k))。而每個(gè)時(shí)間點(diǎn)之間的 k 值不一定一樣，但是全部的 k 值加總為 M，即為 meetings 的長(zhǎng)度。因此併查集的部份總體是 O(M × α(M))。
而一開始對(duì)時(shí)間大小排序，因此時(shí)間為 O(M × log(M))。同時(shí)最後求得答案需要掃過所有人，因此時(shí)間為 O(n)。
因此總體時(shí)間複雜度為 O(M × log(M)) + O(M × α(M)) + O(n) = O(M × log(M) + n)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
