📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 9033| 回复: 30
跳转到指定楼层
上一主题 下一主题
收起左侧

[树/链表/图] 求教Airbnb的graph traversal问题

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Airbnb有这样一道题, 就是一个有向图, 求出最少需要的点能遍历整个图。可是貌似网上的答案是错的,过不了下面这个case, 泪奔!谁能提供一个正确解的?多谢多谢!

O->O->O->O. From 1point 3acres bbs
^               |. 鍥磋?鎴戜滑@1point 3 acres
|     O         |
|     ^         |
|     |         V
O<-O<-O<-O

上一篇:寻算法辅导
下一篇:G家面试该怎么准备啊
推荐
magicsets 2018-2-16 06:44:43 | 只看该作者
全局:
本帖最后由 magicsets 于 2018-2-16 06:46 编辑

先计算SCC,然后将每个SCC合并到一个节点,这样原图就简化为一个DAG(有向无环图),然后求这个简化后的DAG中有多少in-degree为0的点就可以了吧

不过实际写的时候可以不做“合并”这一步,参考代码:
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.HashMap;
  4. import java.util.HashSet;
  5. import java.util.Stack;

  6. public class Solution {
  7.   public static void main(String[] args) {
  8.     Graph g1 = new Graph();
  9.     // O ---> O
  10.     // ^      |
  11.     // |      v
  12.     // O <--- O ---> O
  13.     g1.addEdge(1, 2);
  14.     g1.addEdge(2, 3);
  15.     g1.addEdge(3, 4);
  16.     g1.addEdge(3, 5);
  17.     g1.addEdge(4, 1);

  18.     System.out.println("Result = " + g1.zeroInDegreeNodesWithRegardToSCC());
  19.     // Result = 1


  20.     Graph g2 = new Graph();
  21.     // O ---> O
  22.     // |
  23.     // v
  24.     // O
  25.     g2.addEdge(1, 2);
  26.     g2.addEdge(1, 3);

  27.     System.out.println("Result = " + g2.zeroInDegreeNodesWithRegardToSCC());
  28.     // Result = 1


  29.     Graph g3 = new Graph();
  30.     // O <--- O
  31.     // ^
  32.     // |
  33.     // O
  34.     g3.addEdge(2, 1);
  35.     g3.addEdge(3, 1);

  36.     System.out.println("Result = " + g3.zeroInDegreeNodesWithRegardToSCC());
  37.     // Result = 2


  38.     Graph g4 = new Graph();
  39.     // O <--- O    O ---> O
  40.     // |      ^    ^      |
  41.     // v      |    |      v
  42.     // O ---> O    O ---> O
  43.     g4.addEdge(1, 2);
  44.     g4.addEdge(2, 3);
  45.     g4.addEdge(3, 4);
  46.     g4.addEdge(4, 1);
  47.     g4.addEdge(5, 6);
  48.     g4.addEdge(6, 7);
  49.     g4.addEdge(7, 8);
  50.     g4.addEdge(8, 5);

  51.     System.out.println("Result = " + g4.zeroInDegreeNodesWithRegardToSCC());
  52.     // Result = 2
  53.   }
  54. }

  55. class Graph {
  56.   private HashSet<Integer> nodes = new HashSet<Integer>();
  57.   private HashMap<Integer, HashSet<Integer>> edges =
  58.       new HashMap<Integer, HashSet<Integer>>();

  59.   public void addNode(int node) {
  60.     nodes.add(node);
  61.   }

  62.   public void addEdge(int src, int dst) {
  63.     nodes.add(src);
  64.     nodes.add(dst);

  65.     HashSet<Integer> list = edges.get(src);
  66.     if (list == null) {
  67.       list = new HashSet<Integer>();
  68.       edges.put(src, list);
  69.     }
  70.     list.add(dst);
  71.   }

  72.   public int zeroInDegreeNodesWithRegardToSCC() {
  73.     SCCReverseIndex sccIndex = new SCCReverseIndex(getSCC());
  74.     HashSet<Integer> exNodes = new HashSet<Integer>();

  75.     for (Integer node : nodes) {
  76.       HashSet<Integer> neighbors = edges.get(node);
  77.       if (neighbors != null) {
  78.         for (Integer nb : neighbors) {
  79.           if (!sccIndex.areStronglyConnected(node, nb) ||
  80.               !sccIndex.isHeader(nb)) {
  81.             exNodes.add(nb);
  82.           }
  83.         }
  84.       }
  85.     }

  86.     int count = 0;
  87.     for (Integer node : nodes) {
  88.       if (!exNodes.contains(node)) {
  89.         ++count;
  90.       }
  91.     }
  92.     return count;
  93.   }

  94.   // ------------------------------------------------------------------------
  95.   // 用Tarjan算法计算Strongly Connected Components.
  96.   // https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

  97.   private enum Status {
  98.     kUnvisited,
  99.     kVisiting,
  100.     kVisited
  101.   }

  102.   private static class SCCInfo {
  103.     int index;
  104.     int lowlink;
  105.     Status status = Status.kUnvisited;

  106.     void init(int index) {
  107.       this.index = index;
  108.       this.lowlink = index;
  109.     }
  110.   }

  111.   private static class Context {
  112.     int index = 0;
  113.     Stack<Integer> stack = new Stack<Integer>();
  114.     HashMap<Integer, SCCInfo> sccInfo = new HashMap<Integer, SCCInfo>();
  115.     ArrayList<HashSet<Integer>> sccs = new ArrayList<HashSet<Integer>>();
  116.   }

  117.   public ArrayList<HashSet<Integer>> getSCC() {
  118.     Context ctx = new Context();
  119.     for (Integer node : nodes) {
  120.       ctx.sccInfo.put(node, new SCCInfo());
  121.     }

  122.     for (Integer node : nodes) {
  123.       if (ctx.sccInfo.get(node).status == Status.kUnvisited) {
  124.         tarjanSCC(node, ctx);
  125.       }
  126.     }
  127.     return ctx.sccs;
  128.   }

  129.   private void tarjanSCC(int node, Context ctx) {
  130.     SCCInfo info = ctx.sccInfo.get(node);
  131.     info.init(ctx.index++);
  132.     ctx.stack.push(node);
  133.     info.status = Status.kVisiting;

  134.     HashSet<Integer> neighbors = edges.get(node);
  135.     if (neighbors != null) {
  136.       for (Integer nb : neighbors) {
  137.         SCCInfo nbInfo = ctx.sccInfo.get(nb);
  138.         if (nbInfo.status == Status.kUnvisited) {
  139.           tarjanSCC(nb, ctx);
  140.           info.lowlink = Math.min(info.lowlink, nbInfo.lowlink);
  141.         } else {
  142.           info.lowlink = Math.min(info.lowlink, nbInfo.index);
  143.         }
  144.       }
  145.     }

  146.     if (info.lowlink == info.index) {
  147.       HashSet<Integer> scc = new HashSet<Integer>();
  148.       int curr;
  149.       do {
  150.         curr = ctx.stack.pop();
  151.         ctx.sccInfo.get(curr).status = Status.kVisited;
  152.         scc.add(curr);
  153.       } while (curr != node);
  154.       ctx.sccs.add(scc);
  155.     }
  156.   }
  157. }

  158. // 用于查询node在哪个SCC中的索引
  159. class SCCReverseIndex {
  160.   private HashMap<Integer, Integer> index = new HashMap<Integer, Integer>();

  161.   public SCCReverseIndex(ArrayList<HashSet<Integer>> sccs) {
  162.     for (HashSet<Integer> scc : sccs) {
  163.       Integer label = Collections.min(scc);
  164.       for (Integer node : scc) {
  165.         index.put(node, label);
  166.       }
  167.     }
  168.   }

  169.   public boolean areStronglyConnected(int lhs, int rhs) {
  170.     return index.get(lhs) == index.get(rhs);
  171.   }

  172.   public boolean isHeader(int node) {
  173.     return index.get(node) == node;
  174.   }
  175. }
复制代码

评分

参与人数 5大米 +26 收起 理由
agraynel + 2 给你点个赞!
linbianxiaocao + 1 给你点个赞!
v3dad + 3 给你点个赞!
perlin + 15 握草好认真的回答
14417335 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

推荐
 楼主| flykite083 2018-2-16 10:12:52 | 只看该作者
全局:
求最少的点可以遍历所有点 举个例子:
给出有向图
1->2
2->3
3->4
1->5.
只要走到1,就可以从1走到剩余其他所有点,所以答案就是最少要走1个点,
回复

使用道具 举报

推荐
magicsets 2018-2-16 09:26:15 | 只看该作者
全局:
magicsets 发表于 2018-2-16 09:06
这里对题目的理解有歧义吧,我搜了一下类似的面经:
http://www.1point3acres.com/bbs/thread-216157-1- ...

此外,Airbnb出这个题,几乎不可能使用第二种理解,因为太“难”了 —— 不是说写一个暴力搜索算法难,而是题目本身作为一个比哈密尔顿通路更复杂的问题,在没有实际应用背景的情况下去求最优解(而不是近似最优解),然后写出一个能处理节点数量不超过两位数的暴力算法,这样的题目光是出出来就很丑陋...
回复

使用道具 举报

🔗
 楼主| flykite083 2018-2-13 12:03:26 | 只看该作者
全局:
自己顶一下,看到的答案貌似要么是SCC, 要么是DFS, 可是貌似都过不了上面的case以及(1, 2), (1, 3)这种分叉的case.

求教求教~
回复

使用道具 举报

🔗
 楼主| flykite083 2018-2-16 08:38:04 | 只看该作者
全局:
magicsets 发表于 2018-2-16 06:44
先计算SCC,然后将每个SCC合并到一个节点,这样原图就简化为一个DAG(有向无环图),然后求这个简化后的DAG ...

多谢回复!不过这儿我有个疑问,对于graph g2, (1, 2)和(1, 3), 答案应该是2个点吧?因为只取1的话,1每次要么只能走2这条路,要么只能走3这条路,不能一次走完,所以答案应该要么是1,2,要么是1,3这两个点?
回复

使用道具 举报

🔗
magicsets 2018-2-16 09:06:07 | 只看该作者
全局:
flykite083 发表于 2018-2-16 08:38
多谢回复!不过这儿我有个疑问,对于graph g2, (1, 2)和(1, 3), 答案应该是2个点吧?因为只取1的话,1每 ...

这里对题目的理解有歧义吧,我搜了一下类似的面经:
http://www.1point3acres.com/bbs/thread-216157-1-1.html
http://www.1point3acres.com/bbs/thread-212885-1-1.html
http://www.1point3acres.com/bbs/thread-209537-1-1.html

第一种理解:
寻找图的一个最小节点子集S,使得图中的任何一个节点都可以由S中的某个节点出发沿某条路径到达。

第二种理解:
寻找一个最小路径集合T,使得图中的任何一个节点都在T中的某条路径中,且任意一个节点只能被某一条路径经过一次。


你举的例子是用的第二种理解,而上面的三个帖子中的两个以及我写的答案是第一种理解。

在第二种理解下,这个问题是NP-Hard的,因为你可以把“寻找哈密尔顿通路”这一NP-Hard问题reduce到该问题。代码写出来一定是暴力搜索算法,并不是简单的DFS可以解决的。
回复

使用道具 举报

🔗
 楼主| flykite083 2018-2-16 10:12:26 | 只看该作者
全局:
magicsets 发表于 2018-2-16 09:06
这里对题目的理解有歧义吧,我搜了一下类似的面经:
http://www.1point3acres.com/bbs/thread-216157-1- ...

多谢多谢!这就make sense了!看来是我想复杂了。

"求最少的点可以遍历所有点 举个例子:. 涓
回复

使用道具 举报

🔗
magicsets 2018-2-16 14:35:41 | 只看该作者
全局:
本帖最后由 magicsets 于 2018-2-16 14:37 编辑
flykite083 发表于 2018-2-16 10:12
求最少的点可以遍历所有点 举个例子:
给出有向图
1->2

是的是的
回复

使用道具 举报

🔗
tmtgds 2018-2-19 16:51:13 | 只看该作者
全局:
这题写个Union Find应该也可以吧?return number of connected component
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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