【C++BFS算法】2192. 有向无环图中一个节点的所有祖先

CSDN 2024-08-01 16:35:01 阅读 89

本文涉及知识点

C++BFS算法

LeetCode2192. 有向无环图中一个节点的所有祖先

给你一个正整数 n ，它表示一个有向无环图中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有祖先，这些祖先节点升序排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的祖先节点。

示例 1：

输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]

输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]

解释：

上图为输入所对应的图。

节点 0 ，1 和 2 没有任何祖先。节点 3 有 2 个祖先 0 和 1 。节点 4 有 2 个祖先 0 和 2 。节点 5 有 3 个祖先 0 ，1 和 3 。节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。节点 7 有 4 个祖先 0 ，1 ，2 和 3 。

示例 2：

输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]

解释：

上图为输入所对应的图。

节点 0 没有任何祖先。节点 1 有 1 个祖先 0 。节点 2 有 2 个祖先 0 和 1 。节点 3 有 3 个祖先 0 ，1 和 2 。节点 4 有 4 个祖先 0 ，1 ，2 和 3 。

提示：

1 <= n <= 1000

0 <= edges.length <= min(2000, n * (n - 1) / 2)

edges[i].length == 2

0 <= fromi, toi <= n - 1

fromi != toi

图中不会有重边。

图是有向且无环的。

C++BFS

本问题

⟺

\iff

⟺ 求各节点的后代，BFS各节点的层次，层次不是-1，就是后代。求一个节点后代的时间复杂度：O(m) ,m = edges.length，总时间复杂度为：O(nm)。空间复杂度：O(m)，每次求节点后代，都重新分配内存。

代码

核心代码

<code>class CBFSLeve {

public :

static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {

vector<int> leves(neiBo.size(), -1);

for (const auto& s : start) {

leves[s] = 0;

}

for (int i = 0; i < start.size(); i++) {

for (const auto& next : neiBo[start[i]]) {

if (-1 != leves[next]) { continue; }

leves[next] = leves[start[i]]+1;

start.emplace_back(next);

}

return leves;

}

};

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>> 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<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {

auto neiBo = CNeiBo::Two(n, edges, true);

vector<vector<int>> ret(n);

for (int i = 0; i < n; i++) {

auto leve = CBFSLeve::Leve(neiBo, { i });

for (int j = 0; j < leve.size(); j++) {

if (leve[j]<=0) { continue; }

ret[j].emplace_back(i);

}

return ret;

}

};

单元测试

int n;

vector<vector<int>> edgeList;

TEST_METHOD(TestMethod1)

{

n = 2, edgeList = { { 0,1} };