贡献一道G家onsite题吧 - 未名空间(mitbbs.com)
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
http://shibaili.blogspot.com/2015/07/google-interview-questions-2.html
需要建立有向图 #1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
搜索与回溯
顺着走，走过的就拿开，如果下一步有几种可能，选一个，终止条件是所有的线段都用
掉。走不下去了就回到上一次的选择选没用过的选项，再往下走。
这东西就是个有向图，而且已经把所有的 edge 给你了。把图建好，然后不管是 DFS 还
是 BFS 都能找到起点到终点的路径（前提是存在）
Read full article from 贡献一道G家onsite题吧 - 未名空间(mitbbs.com)
给一个起点，一个终点，然后已知这个人从起点到终点的所有线段，但是打乱了，要你
复原走的路线。
难点是路线里面可能有Cycle，而且会重复。
比如给的是A-->F
线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F
复原结果是 A B C D E B C F
http://shibaili.blogspot.com/2015/07/google-interview-questions-2.html
需要建立有向图 #1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连
搜索与回溯
顺着走，走过的就拿开，如果下一步有几种可能，选一个，终止条件是所有的线段都用
掉。走不下去了就回到上一次的选择选没用过的选项，再往下走。
这东西就是个有向图，而且已经把所有的 edge 给你了。把图建好，然后不管是 DFS 还
是 BFS 都能找到起点到终点的路径（前提是存在）
Read full article from 贡献一道G家onsite题吧 - 未名空间(mitbbs.com)
