beats 100%
Intuition\n\n\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- T
# Intuition\n![image.png](https://assets.leetcode.com/users/images/430884ee-c3fb-4d00-b527-d9fe14463a1b_1719633919.0534906.png)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code C++\n```\n#pragma GCC target("avx,mmx,sse2,sse3,sse4")\nauto _=[]()noexcept{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();\nint adj[1000][1000];\nint asz[1000];\nclass Solution {\n  int sz;\n  vector<int> tmp;\n  void update(vector<vector<int>> &r,int ind){\n    if(!r[ind].empty()) return;\n    if(asz[ind]==0) return;\n    const auto &nei=adj[ind];\n    for(int i=0;i<asz[ind];++i) update(r,nei[i]);\n    auto &v=r[ind];\n    for(int i=0;i<asz[ind];++i) v.emplace_back(nei[i]);\n    for(int i=0;i<asz[ind];++i) combine(v,r[nei[i]]);\n  }\n  void combine(vector<int> &a,const vector<int> &b){\n    int sza=a.size(),szb=b.size(),i=0,j=0;\n    tmp.clear();\n    while(i<sza&&j<szb){\n      if(a[i]==b[j]){tmp.emplace_back(a[i]);++i,++j;}\n      else if(a[i]<b[j]){tmp.emplace_back(a[i]);++i;}\n      else {tmp.emplace_back(b[j]);++j;}\n    }\n    for(;i<sza;++i) tmp.emplace_back(a[i]);\n    for(;j<szb;++j) tmp.emplace_back(b[j]);\n    swap(a,tmp);\n  }\npublic:\n  vector<vector<int>> getAncestors(int n,const vector<vector<int>>& edges) {\n    memset(asz,0,n*sizeof(asz[0]));\n    sz=n;\n    for(const auto &v:edges) adj[v[1]][asz[v[1]]++]=v[0];\n    for(int i=0;i<n;++i) sort(adj[i],adj[i]+asz[i]);\n    vector<vector<int>> r(n);\n    for(int i=0;i<n;++i) update(r,i);\n    return r;\n  }\n}; //if you upvote this you will get good news in 1 hour\n```\n# Code Python3\n```\nclass Solution:\n    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        result = [set() for _ in range(n)]\n        indegrees = [0] * n\n        adj_list = collections.defaultdict(list)\n        for u, v in edges:\n            adj_list[u].append(v)\n            indegrees[v] += 1\n        queue = deque()\n        for i in range(len(indegrees)):\n            if not indegrees[i]:\n                queue.append(i)\n        while queue:\n            node = queue.popleft()\n            for neighbor in adj_list[node]:\n                result[neighbor].update(result[node], [node])\n                indegrees[neighbor] -= 1\n                if not indegrees[neighbor]:\n                    queue.append(neighbor)\n            result[node] = sorted(result[node])\n        return result\n#if you upvote this you will get a good news in 1 hour \n```\n
['C++', 'Python3']