題目連結:
題目大意:
輸入第一列給定兩正整數 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)去找每個連通元件。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。