ETH官方钱包

前往
大廳
主題

ZeroJudge - f670: FJCU_109_Winter_Day1_Lab5 連通塊數量 解題心得

Not In My Back Yard | 2021-02-27 00:00:06 | 巴幣 0 | 人氣 298

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M (0 ≦ N ≦ 10 , 0 ≦ M ≦ N(N - 1) ÷ 2),代表有一個簡單無向圖,其節點數為 N 個(編號為 1 ~ N)、邊有 M 條。

接著有 M 列輸入,每列給定兩個正整數 s 、 t (1 ≦ s 、t ≦ N),代表節點 s 與節點 t 之間有一條邊。

試問給定的圖有多少個連通元件(Connected Component)?

注:簡單圖為沒有自環(指向自己的邊)和重邊(起點與終點一樣的邊)的圖。而連通元件為原圖的一個子圖,其滿足該子圖的任意節點可以經由某路徑到子圖中的其他節點,且節點數盡量地多。



範例輸入:
7 5
1 2
2 3
3 4
2 4
5 6


範例輸出:
3


解題思維:
其實就是這題的「團體」,建好圖的每個邊之後用深度優先搜尋(Depth First Search,DFS)、廣度優先搜尋(Breadth First Search,BFS)去找每個連通元件。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作