Brute force to optimal | C++
O(n log n) \n\nclass Solution {\n    void dfs(int node, vector<int> adj[], vector<int> &vis, vector<set<int>> &ancs) {\n        vis[node] = 1;\n        for(int 
# O(n log n) \n```\nclass Solution {\n    void dfs(int node, vector<int> adj[], vector<int> &vis, vector<set<int>> &ancs) {\n        vis[node] = 1;\n        for(int ad : adj[node]) {\n            if(!vis[ad]) dfs(ad, adj, vis, ancs);\n            ancs[node].insert(ancs[ad].begin(), ancs[ad].end()), ancs[node].insert(ad);\n        }\n    }\n\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<int> adj[n];\n        for(auto e : edges) adj[e[1]].push_back(e[0]);\n\n        vector<set<int>> ancs(n, set<int>());\n        vector<int> vis(n, 0);\n        for(int i=0; i<n; i++) {\n            if(!vis[i]) dfs(i, adj, vis, ancs);\n        }\n        vector<vector<int>> ans;\n        for(auto s : ancs) {\n            vector<int> v(s.begin(), s.end());\n            ans.push_back(v);\n        }\n        return ans;\n    }\n};\n```\n\n# O(n ^ 2)\n```\nclass Solution {\n    void dfs(int node, vector<int> adj[], vector<vector<int>> &ans, int &sp) {\n        for(int ad : adj[node]) {\n            if(!ans[ad].size() || ans[ad].back() != sp) ans[ad].push_back(sp);\n            dfs(ad, adj, ans, sp);\n        }\n    }\n\npublic:\n    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {\n        vector<int> adj[n];\n        for(auto e : edges) adj[e[0]].push_back(e[1]);\n\n        vector<vector<int>> ans(n, vector<int>());\n        for(int i=0; i<n; i++) dfs(i, adj, ans, i);\n        \n        return ans;\n    }\n};\n```\n
['Depth-First Search', 'Ordered Set', 'C++']