重新规划路线（python）

问题描述

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。

路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。

今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。

请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。

题目数据保证每个城市在重新规划路线方向后都能到达城市 0 。
例子

image.png

思路：类似广度优先搜索的思想，从初始节点开始，然后遍历与其相邻的节点，然后再遍历这些节点的相邻节点。而这题遍历的时候去考虑边的情况，如果该边指向的是他前一个节点，则符合，反之，则不符合，需要变更方向。

python实现：

1，队列（超出时间限制）

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        c=connections
        que=[0]#存储需要遍历的节点
        res=0
        while que:                      #判断节点是否全部遍历完
            x=que.pop()                 #出队列
            k=0
            while k<len(c):             #遍历所有的边
                if c[k][1]==x:          #边指向之前节点
                    que.append(c[k][0]) #加入下一节点
                    c.pop(k)            #将遍历的边删除
                    continue            #继续下一次遍历
                elif c[k][0]==x:        
                    res+=1              #变更次数加一
                    que.append(c[k][1])
                    c.pop(k)
                    continue
                k+=1
        return res

改进第一种方法

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        c=connections
        ans = 0
        now = {0}                   #存储需要遍历的节点的集合
        while len(now) != n:        #判断集合长度是否达到n
            new = set()             #新建集合
            i = 0                   
            while i < len(c):       #遍历存储边的列表
                if c[i][1] in now:  
                    new.add(c[i][0])#将下次要遍历的节点保存起来
                    c.pop(i)        #删除边
                    continue
                elif c[i][0] in now:
                    ans += 1
                    new.add(c[i][1])
                    c.pop(i)
                    continue
                i += 1
            now |= new              #将集合new加进集合now中
        return ans

继续改进

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        res = 0
        ordered_set = {0}  # 保存已经能正确到达0的城市
        for (l, r) in connections:
            if r in ordered_set:  # r是已经能到0的城市，那么l->r后就可到0
                ordered_set.add(l)
            elif l in ordered_set:  # r目前不可到城市0，l可到，那就让r->l后到0，重修+1
                res += 1
                ordered_set.add(r)
        return res

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero

最后编辑于：2020.05.31 15:28:13