https://leetcode.cn/problems/minimum-degree-of-a-connected-trio-in-a-graph/description/

最開(kāi)始的思路很簡(jiǎn)單，先記錄每個(gè)節(jié)點(diǎn)的邊，再篩選并記錄能夠構(gòu)成三元組的節(jié)點(diǎn)，最后三元組節(jié)點(diǎn)的總邊數(shù)減去6就是需求的度數(shù)，返回所有三元組度數(shù)的最小值就好了。

顯然，具有很高的復(fù)雜度，不出意料地超時(shí)。

首先，記錄三元組時(shí)，沒(méi)有必要采用字典這種結(jié)構(gòu)，用矩陣就可以了；這樣同時(shí)也不需要額外保存每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)；搜索時(shí)，原本為了保證元組不重復(fù)，對(duì)結(jié)果進(jìn)行了排序，但在采用矩陣的基礎(chǔ)上，直接搜索上三角矩陣就可以了。

空間復(fù)雜度n方，時(shí)間復(fù)雜度記錄為n，搜索為n立方，即n立方。

搜索上三角矩陣，類(lèi)似于將原無(wú)向圖變更為小序號(hào)向大序號(hào)的有向圖。如果直接以序號(hào)構(gòu)建有向圖會(huì)如何？

枚舉 i?以及 i指向的節(jié)點(diǎn) j。由于圖中有 m 條邊，這一部分的時(shí)間復(fù)雜度為 O(m)；

枚舉 j?指向的節(jié)點(diǎn) k，這一部分的時(shí)間復(fù)雜度依舊為 O(m)；

判斷 k?在原始無(wú)向圖中是否與 i 之間有一條無(wú)向邊，使用哈希表，時(shí)間復(fù)雜度為 O(1)。

所以是O(n+m2)，而m在最壞的情況下等于n方……

要使用有向圖來(lái)解決這個(gè)問(wèn)題，要解決枚舉j指向的節(jié)點(diǎn)k的時(shí)間復(fù)雜度問(wèn)題。

上面依據(jù)序號(hào)排序，那么依據(jù)度數(shù)排序制作有向圖也是可以想到的。但其時(shí)間復(fù)雜度和三元組的可遍歷性需要證明。

關(guān)于可遍歷性，對(duì)于三元組，一定存在有向連接按順序遍歷三元組的每個(gè)節(jié)點(diǎn)，而在枚舉 i?以及 i指向的節(jié)點(diǎn) j時(shí)，每個(gè)節(jié)點(diǎn)都得到了遍歷，因此必定能遍歷所有三元組；

關(guān)于時(shí)間復(fù)雜度：

使用反證法，假設(shè)節(jié)點(diǎn) i 的出度大于 sqrt{2m}?，那么節(jié)點(diǎn)i在原始無(wú)向圖中的度數(shù)大于sqrt{2m} ，說(shuō)明其指向的節(jié)點(diǎn)在原始無(wú)向圖中的度數(shù)也大于 sqrt{2m} ，即原始無(wú)向圖中有超過(guò) sqrt{2m} 個(gè)節(jié)點(diǎn)的度數(shù)大于 sqrt{2m} ，即總度數(shù)大于 2m。而總度數(shù)應(yīng)該恰好為 2m。

時(shí)間復(fù)雜度為O(n+m*sqrt{m})，最壞的情況下為O(n立方)。