Question discussion

How many different topological orderings does the DAG with edges A→C, B→C, C→D, B→E and E→D have?

1733Medium DSSSB TGT Computer Science 0 replies 1 views
0

How many different topological orderings does the DAG with edges A→C, B→C, C→D, B→E and E→D have?

  • A3
  • B4
  • C5
  • D6
Correct answer: C

Explanation

D must come last, and the orders of A, B, C, E with A and B before C and B before E are ABCE, ABEC, BACE, BAEC and BEAC, i.e. 5.

Discussion 0

Nobody has replied yet. Start the discussion!