You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
82 lines
2.7 KiB
82 lines
2.7 KiB
/*
|
|
问题描述：
|
|
有向无环图中一个节点的所有祖先。
|
|
给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
|
|
给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
|
|
请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
|
|
如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。
|
|
|
|
输入：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 。
|
|
*/
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
class Solution {
|
|
public:
|
|
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
|
|
vector<unordered_set<int>> anc(n); // 存储每个节点祖先的辅助数组
|
|
vector<vector<int>> e(n); // 邻接表
|
|
vector<int> indeg(n); // 入度表
|
|
// 预处理
|
|
for (const auto& edge: edges) {
|
|
e[edge[0]].push_back(edge[1]);
|
|
++indeg[edge[1]];
|
|
}
|
|
// 广度优先搜索求解拓扑排序
|
|
queue<int> q;
|
|
for (int i = 0; i < n; ++i) {
|
|
if (!indeg[i]) {
|
|
q.push(i);
|
|
}
|
|
}
|
|
while (!q.empty()) {
|
|
int u = q.front();
|
|
q.pop();
|
|
for (int v: e[u]) {
|
|
// 更新子节点的祖先哈希表
|
|
anc[v].insert(u);
|
|
for (int i: anc[u]) {
|
|
anc[v].insert(i);
|
|
}
|
|
--indeg[v];
|
|
if (!indeg[v]) {
|
|
q.push(v);
|
|
}
|
|
}
|
|
}
|
|
// 转化为答案数组
|
|
vector<vector<int>> res(n);
|
|
for (int i = 0; i < n; ++i) {
|
|
for (int j: anc[i]) {
|
|
res[i].push_back(j);
|
|
}
|
|
sort(res[i].begin(), res[i].end());
|
|
}
|
|
return res;
|
|
}
|
|
};
|
|
|
|
int main(){
|
|
Solution test;
|
|
int n = 8;
|
|
//[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
|
|
vector<vector<int>> nums = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
|
|
vector<vector<int>> res = test.getAncestors(n, nums);
|
|
for(int i = 0; i < res.size(); i++){
|
|
for(int j = 0; j < res[i].size(); j++){
|
|
cout << res[i][j];
|
|
}
|
|
cout << endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|