2192 - All Ancestors of a Node in a Directed Acyclic Graph

 JAVA

• class Solution {
      private int n;
      private List<Integer>[] g;
      private List<List<Integer>> ans;
  
      public List<List<Integer>> getAncestors(int n, int[][] edges) {
          g = new List[n];
          this.n = n;
          Arrays.setAll(g, i -> new ArrayList<>());
          for (var e : edges) {
              g[e[0]].add(e[1]);
          }
          ans = new ArrayList<>();
          for (int i = 0; i < n; ++i) {
              ans.add(new ArrayList<>());
          }
          for (int i = 0; i < n; ++i) {
              bfs(i);
          }
          return ans;
      }
  
      private void bfs(int s) {
          Deque<Integer> q = new ArrayDeque<>();
          q.offer(s);
          boolean[] vis = new boolean[n];
          vis[s] = true;
          while (!q.isEmpty()) {
              int i = q.poll();
              for (int j : g[i]) {
                  if (!vis[j]) {
                      vis[j] = true;
                      q.offer(j);
                      ans.get(j).add(s);
                  }
              }
          }
      }
  }

C++

• class Solution {
  public:
      vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
          vector<int> g[n];
          for (auto& e : edges) {
              g[e[0]].push_back(e[1]);
          }
          vector<vector<int>> ans(n);
          auto bfs = [&](int s) {
              queue<int> q;
              q.push(s);
              bool vis[n];
              memset(vis, 0, sizeof(vis));
              vis[s] = true;
              while (q.size()) {
                  int i = q.front();
                  q.pop();
                  for (int j : g[i]) {
                      if (!vis[j]) {
                          vis[j] = true;
                          ans[j].push_back(s);
                          q.push(j);
                      }
                  }
              }
          };
          for (int i = 0; i < n; ++i) {
              bfs(i);
          }
          return ans;
      }
  };