原题链接:Leetcode 2192. 有向无环图中一个节点的所有祖先
class Solution {
public:
vector<vector<int>> adj;
vector<vector<int>> res;
vector<int> indegree;
map<pair<int,int>,int> mp;
void dfs(int now)
{
for(auto x:adj[now])
{
if(!mp[{now,x}])
{
res[now].push_back(x);
mp[{now,x}]=1;
}
if(res[x].size()==0) dfs(x);
for(auto y:res[x])
{
if(!mp[{now,y}])
{
res[now].push_back(y);
mp[{now,y}]=1;
}
}
}
}
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
res.resize(n);
adj.resize(n);
indegree.resize(n);
for(auto x:edges)
{
int a=x[0],b=x[1];
adj[b].push_back(a);
indegree[a]++;
}
for(int i=0;i<n;i++)
{
if(!indegree[i]) dfs(i);
}
for(int i=0;i<n;i++) sort(res[i].begin(),res[i].end());
return res;
}
};
拓扑排序
class Solution {
public:
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
vector<vector<int>> res(n);
vector<int> indegree(n);
vector<set<int>> pre(n);
for(auto x:edges)
{
int a=x[0],b=x[1];
adj[a].push_back(b);
indegree[b]++;
}
queue<int> q;
for(int i=0;i<n;i++)
{
if(!indegree[i]) q.push(i);
}
while(!q.empty())
{
int now=q.front(); q.pop();
for(auto x:adj[now])
{
indegree[x]--;
pre[x].insert(pre[now].begin(),pre[now].end());
pre[x].insert(now);
if(!indegree[x]) q.push(x);
}
}
for(int i=0;i<n;i++)
{
res[i].insert(res[i].end(),pre[i].begin(),pre[i].end());
}
return res;
}
};