本文涉及知识点
图论 深度优先搜索 有向图 无向图 树
LeetCode2858. 可以到达每一个节点的最少边反转次数
给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。
给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。
边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。
对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别 独立 计算 最少 需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。
示例 1：
输入：n = 4, edges = [[2,0],[2,1],[1,3]]
输出：[1,1,0,2]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 1 。
对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。
所以 answer[1] = 1 。
对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[2] = 0 。
对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。
所以 answer[3] = 2 。
示例 2：
输入：n = 3, edges = [[1,2],[2,0]]
输出：[2,0,1]
解释：上图表示了与输入对应的简单有向图。
对于节点 0 ：反转 [2,0] 和 [1,2] ，从节点 0 出发可以到达所有节点。
所以 answer[0] = 2 。
对于节点 1 ：不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[1] = 0 。
对于节点 2 ：反转 [1,2] ，从节点 2 出发可以到达所有节点。
所以 answer[2] = 1 。
提示：
2 <= n <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ui == edges[i][0] < n
0 <= vi == edges[i][1] < n
ui != vi
输入保证如果边是双向边，可以得到一棵树。
深度优先搜索
如果这些边是双向边，那么这个图形成一棵 树 → \rightarrow→ 无环。如果一棵树，所有的边，都由父节点指向子节点，则无需反转；有多少边反向，就需要翻转多少次。 计算root的反向边的时间复杂度是O(n)。
性质一： root是树的根节点，child是它的子节点，将child转成根节点，除了 root 和 child 的父子互换外，其它父子关系不变。
大致流程
一，DFS 到各节点的父节点。
二，记录各节点和父节点组成的边，是指向父节点，还是反向。
三，DFS换根。
代码
代码
把DFS中的bool转整形，直接改成整形，用时变成1/3。
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) { vector<vector<int>> vNeiBo(rCount * cCount); auto Move = [&](int preR, int preC, int r, int c) { if ((r < 0) || (r >= rCount)) { return; } if ((c < 0) || (c >= cCount)) { return; } if (funVilidCur(preR, preC) && funVilidNext(r, c)) { vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c); } }; for (int r = 0; r < rCount; r++) { for (int c = 0; c < cCount; c++) { Move(r, c, r + 1, c); Move(r, c, r - 1, c); Move(r, c, r, c + 1); Move(r, c, r, c - 1); } } return vNeiBo; } static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat) { vector<vector<int>> neiBo(neiBoMat.size()); for (int i = 0; i < neiBoMat.size(); i++) { for (int j = i + 1; j < neiBoMat.size(); j++) { if (neiBoMat[i][j]) { neiBo[i].emplace_back(j); neiBo[j].emplace_back(i); } } } return neiBo; } }; class Solution { public: vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) { m_vToParent.resize(n); m_vToChild.resize(n); m_vAns.resize(n); m_vParent.assign(n, -2); auto vNeiBo = CNeiBo::Two(n, edges, false); DFS1(0, -1, vNeiBo); for (const auto& v : edges) { if (v[1] == m_vParent[v[0]]) { m_vToParent[v[0]] = 1;//v[0]指向父亲的边存在 } if (v[0] == m_vParent[v[1]]) { m_vToChild[v[1]] = 1;//父亲指向v[0]的边存在 } } m_vAns[0] = n - 1 - std::count(m_vToChild.begin(), m_vToChild.end(), 1); DFS2(0, -1, vNeiBo); return m_vAns; } void DFS1(int cur, int par, const vector<vector<int>>& vNeiBo) { m_vParent[cur] = par; for (const auto& next : vNeiBo[cur]) { if (-2 != m_vParent[next]) { continue; } DFS1(next, cur, vNeiBo); } } void DFS2(int cur, int par, const vector<vector<int>>& vNeiBo) { if (-1 != par) { m_vAns[cur] = m_vAns[par] - (1-m_vToChild[cur]) + (1-m_vToParent[cur]); } for (const auto& next : vNeiBo[cur]) { if (m_vParent[next] != cur) { continue; } DFS2(next, cur, vNeiBo); } } vector<int> m_vAns; vector<int> m_vParent; vector<int> m_vToParent, m_vToChild; };
代码二
力扣平台上： dfs中 m_vDirectNeiBo[par].count(i) 的用时是非DFS中的8倍。
class CNeiBo { public: static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<int>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase); } } return vNeiBo; } static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) { vector<vector<std::pair<int, int>>> vNeiBo(n); for (const auto& v : edges) { vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]); if (!bDirect) { vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]); } } return vNeiBo; } static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext) { vector<vector<int>> vNeiBo(rCount * cCount); auto Move = [&](int preR, int preC, int r, int c) { if ((r < 0) || (r >= rCount)) { return; } if ((c < 0) || (c >= cCount)) { return; } if (funVilidCur(preR, preC) && funVilidNext(r, c)) { vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c); } }; for (int r = 0; r < rCount; r++) { for (int c = 0; c < cCount; c++) { Move(r, c, r + 1, c); Move(r, c, r - 1, c); Move(r, c, r, c + 1); Move(r, c, r, c - 1); } } return vNeiBo; } static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat) { vector<vector<int>> neiBo(neiBoMat.size()); for (int i = 0; i < neiBoMat.size(); i++) { for (int j = i + 1; j < neiBoMat.size(); j++) { if (neiBoMat[i][j]) { neiBo[i].emplace_back(j); neiBo[j].emplace_back(i); } } } return neiBo; } }; class Solution { public: vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) { m_vDirectNeiBo.resize(n); m_vAns.resize(n); m_vParent.assign(n, -2); m_vLeve.resize(n); for (const auto& v : edges) { m_vDirectNeiBo[v[0]].emplace(v[1]); } auto vNeiBo = CNeiBo::Two(n, edges, false); int clock1 = clock(); DFS(0, -1, vNeiBo); int clock2 = clock(); const int iMaxLeve = *std::max_element(m_vLeve.begin(),m_vLeve.end()); vector<vector<int>> vLeves(iMaxLeve+1); for (int i = 0; i < n; i++) { const int par = m_vParent[i]; if ((-1 != par) && (!m_vDirectNeiBo[par].count(i))) { m_vAns[0]++; } vLeves[m_vLeve[i]].emplace_back(i); } for (const auto& v: vLeves) { for (const auto& cur : v) { const int par = m_vParent[cur]; if (-1 == par) { continue; } m_vAns[cur] = m_vAns[par] - (!m_vDirectNeiBo[par].count(cur)) + (!m_vDirectNeiBo[cur].count(par)); } } int clock3 = clock(); std::cout << (clock2 - clock1) << " " << (clock3 - clock2); return m_vAns; } void DFS(int cur, int par, const vector<vector<int>>& vNeiBo) { m_vParent[cur] = par; if (-1 != par) { m_vLeve[cur] = m_vLeve[par] + 1; } for (const auto& next : vNeiBo[cur]) { if (-2 != m_vParent[next] ) { continue; } DFS(next, cur, vNeiBo); } } vector<unordered_set<int>> m_vDirectNeiBo; vector<int> m_vAns,m_vParent,m_vLeve; };
