aboutsummaryrefslogtreecommitdiff
path: root/ancestors_node_acyclic_graph.cpp
blob: 71b6fb77b0feb3a7854ace800ae6bd345bec16de (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 2192. All Ancestors of a Node in a Directed Acyclic Graph
#include "leetcode.h"

/*
 * given a positive integer 'n' representing the number of nodes of a directed
 * acyclic graph (dag). the nodes are numbered from 0 to 'n - 1' inclusively.
 * you are also given a 2d integer array 'edges' where 'edges[i] = [fromi, toi]'
 * denotes that there is a unidirectional edge from 'fromi' to 'toi' in the
 * graph. return a list 'answer' where 'answer[i]' is the list of ancestors of
 * the i'th node, sorted in ascending order. a node 'u' is an ancestor of
 * another node 'v' if 'u' can reach 'v' via a set of edges.
 */

class Solution {
private:
  void dfs(int x, int curr, vector<vector<int>> &res,
           vector<vector<int>> &direct_child) {
    for (auto &i : direct_child[curr])
      if (!res[i].size() || res[i].back() != x) {
        res[i].push_back(x);
        dfs(x, i, res, direct_child);
      }
  }

public:
  vector<vector<int>> getAncestors(int n, vector<vector<int>> &edges) {
    vector<vector<int>> ans(n), direct_child(n);
    for (auto &i : edges)
      direct_child[i[0]].push_back(i[1]);
    for (int i = 0; i < n; i++)
      dfs(i, i, ans, direct_child);
    return ans;
  }
};

int main() {
  Solution obj;
  vvd e1 = {{0, 3}, {0, 4}, {1, 3}, {2, 4}, {2, 7},
                 {3, 5}, {3, 6}, {3, 7}, {4, 6}};
  vvd e2 = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2},
                 {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}};
  vvd ga1 = obj.getAncestors(8, e1), ga2 = obj.getAncestors(5, e2);
  for (int i = 0; i < ga1.size(); i++) {
    for (int j = 0; j < ga1[0].size(); j++)
      printf("%d ",
             ga1[i][j]); // expect:
                         // [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < ga2.size(); i++) {
    for (int j = 0; j < ga2[0].size(); j++)
      printf("%d ",
             ga2[i][j]); // expect: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
    printf("\n");
  }
  printf("\n");
}