请教一个算法

ArXoR

原帖由 mirnux 于 4/12/07 21:11 发表
先把每次等价对表中的第1个等价对压入一个空链表中，然后以此为树根在等价对表中寻找包含链表中元素的等价对，如果找到，当符合条件的等价对中只有一个元素存在于链表中时，则把另一个元素压入到链表中，并在等价 ...

这个就是一个bfs嘛, 还弄得比较笨拙, 而且其复杂度为O(n^2), 可以轻易地构造出这样的数据.

如果楼主对图, dfs/bfs还不甚知晓的话, 还是静下心找本书来看比较好.

mirnux

好，我现在来看看bfs和STL的list，非常感谢楼上的

mirnux

非常感谢
用bfs完成问题

参考了http://www.yuanma.org/data/2006/0605/article_645.htm
用STL实现DFS/BFS算法

week008

有这么复杂吗？
搞个二维的数组A[][]，读入1，2等价对存放入A[0]， 读入1，3等价等查找数组中是否已经存在，则把3也放入A[0]，再读入2，4等价对，同理把4放入A[0]，再读入5，6等价对，查找之前不存在，则存放入A[1]，..........读完等价对。然后再扫描一下数组看有无重复存放的数字则合并两个数组（比如读入为1＝2，3=4， 2=4， 则会放入到两个数组中，所以要扫描合并一下），最后找出没有被存放的数字另外存放在数组中。搞定。

挺简单的问题，搞的这么复杂。