2024年5月31日 星期五
2024年5月30日 星期四
2024年5月28日 星期二
2024年5月27日 星期一
[785] Is Graph Bipartite?
感覺是一個很老的題目!!!
判斷是不是一個二分圖:在一個無方向graph 裡,如果每一個edge相接的兩個node 分屬不同group,那就是一個二分圖。可以用對node塗色的概念來想!一開始大家都沒有顏色,選一個起始點塗上紅色,和它有edge連接的都塗上綠色。接著往外塗去,如果遇到已經有人上色了的,若是顏色相同,表示這不是一個二分圖。