HW Question: Bipartite Graphs - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

HW Question: Bipartite Graphs

HW Question: Bipartite Graphs# Programming - 葵花宝典

l*i2008-11-17 08:11

1 楼

【以下文字转载自 Salon 讨论区】
发信人: liangzhi (良知), 信区: Salon
标题: 原创讽刺故事: 三十年河东,三十年河西
发信站: BBS 未名空间站 (Thu Jul 31 08:53:29 2008)
原创讽刺故事: 三十年河东,三十年河西
这句话大家都明白,但这句话的起源,恐怕不是每个人都知道的,所以我来八卦一下.
据相声界老前辈考证,天津原来叫陈塘关(现在还有个地方叫陈塘庄,在河西区),陈塘关
的守将就是大名鼎鼎的李天王.李天王可是治军有方,这些在封神演义里有交代.哪吒在
莲藕化身之前的行宫,就在山里,后来李天王操演回家时发现毁掉的.离陈塘关最近的山
应该在蓟县,所以估计李天王每天练兵,至少是在山海关了,由此可见其训练强度之大机
动性能之好了.估计这支部队如果用于汶川救灾,肯定能在震后立即进入重灾区,我就奇
怪温总理怎么就不用呢?
奇怪的是就这样一支王牌部队,又在兴周灭纣时立了不少军功,竟没有一个封神.这倒不
是姜太公偏心眼,制度问题呀,只有战死的才能封神,就连太公本人也没得到神位.李天王
父子倒是后来肉身成神了,可那时小兵们不答应呀.于是集体

s*i2008-11-17 08:11

2 楼

How can I give algorithm that checks whether a graph is bipartite (a graph
whose nodes can be divided into two sets N1 and N2, and every edge is
between a member of N1 and N2)?
And since non-bipartite means there must be a cycle of odd length, how can I
check bipartite, and if false, prints a cycle of odd length?
Thanks in advance.

s*e2008-11-17 08:11

3 楼

DFS

I

【在 s***i 的大作中提到】

: How can I give algorithm that checks whether a graph is bipartite (a graph
: whose nodes can be divided into two sets N1 and N2, and every edge is
: between a member of N1 and N2)?
: And since non-bipartite means there must be a cycle of odd length, how can I
: check bipartite, and if false, prints a cycle of odd length?
: Thanks in advance.