[理工] 中央 102 離散

看板Grad-ProbAsk作者 (我寶貝)時間7年前 (2017/01/17 16:39), 編輯推噓2(2推 0噓 11→)
留言13則, 3人參與, 最新討論串1/1
http://i.imgur.com/wnRWQYb.jpg
就是啊我要問這一題的D選項 想問一下要怎麼判斷有幾個～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.73.245 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484642395.A.69B.html
推
01/17 16:48, , 1F
找articulation point,切開之後就可以看到有多少個
01/17 16:48, 1F
→
01/17 16:48, , 2F
connected component
01/17 16:48, 2F
→
01/17 16:50, , 3F
因為是undirected graph, 所以任2點都存在雙向路徑
01/17 16:50, 3F
→
01/17 16:52, , 4F
可是答案給我1耶
01/17 16:52, 4F
推
01/17 16:52, , 5F
啊啊我講錯了，我講的是Biconnected component
01/17 16:52, 5F
→
01/17 16:53, , 6F
是1沒錯，我講完就覺得怪怪的，connected component我們
01/17 16:53, 6F
→
01/17 16:53, , 7F
通常就當作maximal connected component,這題就是整棵樹
01/17 16:53, 7F
→
01/17 16:53, , 8F
了
01/17 16:53, 8F
→
01/17 16:53, , 9F
原來是這樣 所以不能切
01/17 16:53, 9F
→
01/17 16:53, , 10F
好的謝謝你們
01/17 16:53, 10F
→
01/17 16:54, , 11F
樹是conected graph
01/17 16:54, 11F
→
01/17 16:56, , 12F
只要沒有disjoint set就是connected, 有幾個disjoint se
01/17 16:56, 12F
→
01/17 16:56, , 13F
t就有幾個component
01/17 16:56, 13F
‣ 更多 bemybaby 的文章
文章代碼(AID): #1OVTXRQR (Grad-ProbAsk)