README.md

1466. 重新规划路线

English Version

题目描述

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

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

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

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

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

 

示例 1：

输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出：3
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 2：

输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出：2
解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 3：

输入：n = 3, connections = [[1,0],[2,0]]
输出：0

 

提示：

• 2 <= n <= 5 * 10^4
• connections.length == n-1
• connections[i].length == 2
• 0 <= connections[i][0], connections[i][1] <= n-1
• connections[i][0] != connections[i][1]

解法

方法一：DFS

将图视为无向图。从编号 0 开始 dfs，如果遇到正向边，则需要累加一次变更。

Python3

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def dfs(u):
            vis[u] = True
            ans = 0
            for v in g[u]:
                if not vis[v]:
                    if (u, v) in s:
                        ans += 1
                    ans += dfs(v)
            return ans

        g = defaultdict(list)
        s = set()
        for a, b in connections:
            g[a].append(b)
            g[b].append(a)
            s.add((a, b))
        vis = [False] * n
        return dfs(0)

Java

class Solution {
    public int minReorder(int n, int[][] connections) {
        Map<Integer, List<Pair<Integer, Boolean>>> g = new HashMap<>();
        for (int[] e : connections) {
            int u = e[0], v = e[1];
            g.computeIfAbsent(u, k -> new ArrayList<>()).add(new Pair<>(v, true));
            g.computeIfAbsent(v, k -> new ArrayList<>()).add(new Pair<>(u, false));
        }
        boolean[] vis = new boolean[n];
        return dfs(0, g, vis);
    }

    private int dfs(int u, Map<Integer, List<Pair<Integer, Boolean>>> g, boolean[] vis) {
        vis[u] = true;
        int ans = 0;
        for (Pair<Integer, Boolean> e : g.getOrDefault(u, Collections.emptyList())) {
            int v = e.getKey();
            boolean exist = e.getValue();
            if (!vis[v]) {
                if (exist) {
                    ++ans;
                }
                ans += dfs(v, g, vis);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        unordered_map<int, vector<pair<int, bool>>> g;
        for (auto& e : connections) {
            int u = e[0], v = e[1];
            g[u].push_back({v, true});
            g[v].push_back({u, false});
        }
        vector<bool> vis(n);
        return dfs(0, g, vis);
    }

    int dfs(int u, unordered_map<int, vector<pair<int, bool>>>& g, vector<bool>& vis) {
        vis[u] = true;
        int ans = 0;
        for (auto& p : g[u]) {
            int v = p.first;
            bool exist = p.second;
            if (!vis[v]) {
                if (exist) ++ans;
                ans += dfs(v, g, vis);
            }
        }
        return ans;
    }
};

Go

func minReorder(n int, connections [][]int) int {
	type pib struct {
		v int
		b bool
	}
	g := map[int][]pib{}
	for _, e := range connections {
		u, v := e[0], e[1]
		g[u] = append(g[u], pib{v, true})
		g[v] = append(g[v], pib{u, false})
	}
	vis := make([]bool, n)
	var dfs func(int) int
	dfs = func(u int) int {
		ans := 0
		vis[u] = true
		for _, p := range g[u] {
			v, exist := p.v, p.b
			if !vis[v] {
				if exist {
					ans++
				}
				ans += dfs(v)
			}
		}
		return ans
	}
	return dfs(0)
}

...