一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 509|回复: 1
收起左侧

[算法题] 找出无向图汇总的相连要素 求助

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-8-24 23:08:37 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 jy_121 于 2015-8-24 23:10 编辑

这是lintcode上的一道原题,大意就是把图中相连通的部分放到一个集合里输出:

http://www.lintcode.com/zh-cn/pr ... e-undirected-graph/


我是用了BFS来做,但是其中一个test case里一个集合中的顺序和答案不一样,报错了。但是题目里好像没有这样的要求,不知道是为什么。
代码如下:
  1. public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
  2.         // Write your code here
  3.         List<List<Integer>> result = new ArrayList<List<Integer>> ();
  4.         Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
  5.         HashMap<UndirectedGraphNode, Integer> map
  6.         = new HashMap<UndirectedGraphNode, Integer>();

  7.         
  8.         for(int i = 0; i < nodes.size(); i++){
  9.                 if(map.containsKey(nodes.get(i))){
  10.                         continue;
  11.                 }
  12.                 ArrayList<Integer> list = new ArrayList<Integer>();
  13.                 q.offer(nodes.get(i));
  14.                 map.put(nodes.get(i), 1);
  15.                 while(!q.isEmpty()){
  16.                         UndirectedGraphNode node2 = q.poll();
  17.                         if(!list.contains(node2.label)){
  18.                                 list.add(node2.label);
  19.                         }
  20.                    
  21.                     for(UndirectedGraphNode n : node2.neighbors){
  22.                             if(!map.containsKey(n)){
  23.                                     q.offer(n);
  24.                                 list.add(n.label);
  25.                                 map.put(n, 1);
  26.                         }
  27.                     }
  28.                    
  29.                 }
  30.                
  31.                 result.add(list);
  32.                
  33.         }
  34.         return result;
  35.         
  36.     }
复制代码
这是报错时的截图,谢谢大家了









question.png
 楼主| jy_121 发表于 2015-8-28 11:24:38 | 显示全部楼层
把list排序后就可以通过,估计是题目的要求有些问题。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 23:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表