UVa12783 - Weak Links(DFS、Find Bridge Problem)

題目大意

警察想要拆除犯罪份子的聯繫,會給你一個犯罪分子的聯繫圖,只要我們能夠將這個聯繫圖一分為二,此時他們的消息傳播就會被我們給阻斷。

你的任務就是要找出只要切斷那些犯罪份子的聯繫,就可以讓消息傳播阻斷,輸出總共有幾種切法,並且輸出每一種切法。
並且從最小的犯罪份子(數字代號)開始依序輸出
題目連結

閱讀更多...

演算法知識 - Graph theorm Find Bridge

Find Bridge 介紹

Find Bridge 顧名思義就是要找到橋,那這裡的橋是甚麼意思呢?
想想現實生活中的橋,是不是只要橋斷開了兩邊的聯繫就斷了?

那麼圖論中亦是如此,只要有一個邊斷掉了,那麼就一張圖就被分成兩個圖了!(注意,兩張圖中可能其中有一張圖只有一個點)
師大演算法中有用圖片進行說明,其中我用紅筆圈出來的就是橋。
注意,圖中的 (1,2)、(7,8)、(7,9) 都是橋

而此演算法解出的問題就是讓所有這些橋的點都被找到

閱讀更多...

UVa10505 - Montesco vs Capuleto(DFS、塗色問題)

題目大意

羅密歐與茱麗葉要結婚啦,但他們的雙方家庭是世仇,但他們還是希望可以找雙方家庭的親朋好友來,因此它們避免婚禮之間有衝突,他們邀請的人如下

  • 如果 a 跟 b 是敵人,b 跟 c 也是敵人,d 跟 a,b,c 都不是敵人,那麼 a 跟 c 就是朋友、a 與 d 並不是朋友
  • 如果 a 跟 b 是敵人,雙方都討厭對方
  • 我們只邀請數字小於 N 的人,大於 N 的都不邀請
  • 如果我們邀請 a,那麼 a 以外的所有朋友都要參加,避免被誤會。

現在請告訴羅密歐與茱麗葉,最多有幾個人可以來參加婚禮

題目連結

閱讀更多...
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: