Re: [商管] [資結] 中山-101-資管所
※ 引述《lingcandy (candyling)》之銘言：
: 大家好~~~
: 想請問中山資管所的101資結第7題
: http://ppt.cc/surE
: 它說要以O(m+n)寫一algo判斷是否為 bipartite graph
: 請問要怎麼寫呢 ?
: 我的寫法到要check edge是不是同一集合的時候就要O(n*m)了 QQ
: 謝謝喔!
boolean visit:false未尋訪,true尋訪過
int mark:0沒集合,1位於set1,2位於set2
bipartite(v,type)
{
visit[v]=true;
for each u∈adj[v]
{
if (mark[u]==0) mark[u]=3-type;
else if (mark[u]==type) return false;
if ( ! visit[u])
if ( ! bipartite (u,3-type) return false;
}
return true;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.174.132.195
※ 編輯: movo11 來自: 1.174.132.195 (02/27 20:12)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：