隨著資訊設備的普及，人們開始頻繁地在網路上架設以及使用各式各樣的「社群網站」。而所謂的「社群網站」就是提供大家在網際網路上建立「社群網路 (social network)」的網站。而「社群網路」則是擁有相同興趣或活動的人所構成的群體，每個個體之間由一些互動關係 (interactive relation) 所連接。舉例來說，如果是個交友的社群，連結他們之間關係可能是「朋友關係」，而如果是個由公司內部人員所構成的社群，則可能是「合作關係」。
由於近年來社群網站的數量大幅增加，「社群網路分析 (Social Network Analysis)」這個領域也成為資訊科技中新興崛起的重要領域，其相關的理論和應用也隨之增加。其中一個問題是如何衡量一個社群網路有多健全？所謂的「健全」我們可以當做是「連接得緊密」的意思，也就是說，一個越健全的社群網路，我們越不容易藉由「刪除其中的一些個體」這個動作來拆散該社群網路。
那麼，要怎麼衡量這種「健全度」呢？研究「社群網路分析」學科的專家們對此紛紛提出了許多相關的想法和理論，其中一個是「群聚係數 (Clustering Coefficient, 也稱集聚係數)」，群聚係數 C(G) 的計算方法如下：
3 × (三角形個數)
C(G) =
(連通三點對的個數)
其中 G 即為我們要考慮的社群網路。如果有三個人以 a,b,c 代稱，其中 a 和 b 有互動關係且 b 和 c 也有互動關係的話，我們就稱 (a,b,c) 為一個「連通三點對
(connected triple of vertices)」。需要注意的是，我們視它的反向 (c,b,a) 為「同一個」連通三點對。而對於其他的可能組合，都是和 (a,b,c) 不同的連通三點對。
而如果 (a,b,c) 是一個連通三點對且 a 和 c 也有互動關係的話，則我們說這三個個體 a,b,c 構成一個「三角形 (triangle)」。我們視同樣的三個個體 a,b,c 所組成的三角形為「同一個」三角形，即 (a,b,c)、(a,c,b)、(b,a,c)、(b,c,a)、(c,a,b)、(c,b,a) 這些只能被算一次 (他們是「同一個」三角形)。
現在，給定一個社群網路之中個體之間的互動關係，請你寫一個程式計算出該社群網路的「群聚係數」。
輸入檔的第一行有一個正整數 T (T ≤ 50)，代表總共有幾筆測試資料。
每筆測試資料的第一行有一個整數 N (3 ≤ N ≤ 200)，代表給定的社群網路中有多少個個體 (例如：人數)，我們將個體們分別編號從 1 到 N。第二行則有一個整數
M ，代表給定的社群網路中有幾組互動關係 (例如：朋友關係)。
接著有 M 行描述每組互動關係，每一行有兩個正整數 ai,bi，中間以一個空白隔開，代表編號為 ai 的個體和編號為 bi 的個體有互動關係 (例如：他們是朋友)。每一組互動關係都是「雙向」的 (例如：他們「彼此互為」朋友)。我們保證給定的社群網路中一定至少存在一個連通三點對。
對於每一筆測試資料所給定的社群網路，請輸出一個分數表示該社群網路的「群聚係數」，其格式為 p/q，(p為分子，q為分母)。
請輸出最簡分數 (即 p 與 q 的最大公因數為 1)。如果 p = 0，請輸出 0/1。
3 5 7 1 2 2 3 1 3 3 4 2 4 4 5 1 5 3 3 1 2 3 1 3 2 4 3 1 2 2 3 3 4
6/13 1/1 0/1
對於第一組範例，我們共有 13 個連通三點對：(1,3,2), (1,2,3), (1,2,4), (1,3,4),
(1,5,4), (2,1,3), (2,4,3), (2,3,4), (2,1,5), (2,4,5), (3,2,4), (3,1,5), (3,4,5)，並且有
2 個三角形：(1,2,3), (2,3,4)。所以我們可以得到「群聚係數」(答案) 為 313×2 = 。
對於第二組範例，我們共有 3 個連通三點對：(1,3,2), (1,2,3), (2,1,3)，並且有 1
個三角形 (1,2,3)。所以我們可以得到「群聚係數」(答案) 為 3×31 = 。
對於最後一組範例，我們共有 2 個連通三點對：(1,2,3), (2,3,4)，而我們在這個社群網路中找不到任何三角形 (0 個三角形)。所以我們可以得到「群聚係數」(答案) 為 3×20 = 。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||