complete-dag-question.md

1. What does well-connected mean?

2. Construct a directed-acyclic-graph (DAG) with approximately 100,000 randomly generated vertices and 99,999 randomly generated edges.
   Which means:
   100k vertices and 99,999 edges are randomly generated beforehand.
   Then we will use these 100k vertices and 99,999 edges to construct a complete DAG.
   This can lead to a complete DAG which has <= 100k vertices and <= 99,999 edges.
   Because when we generate edges, there might be a couple of edges which cause a cycle.
   For example: Vertex (4) and Vertex (7). We random generated 2 edges (4)-->(7) and (7)-->(4). And if this happens, it will leave a vertex which has no edge to connect to another vertex because we only have N vertices and N-1 edges.
   OR
   We will construct a complete DAG which has exactly 100k vertices and 99,999 edges.

---

Example: We generated 5 Vertices, and 4 egdes. What is the correct output? The Output (1) or Output (2) or another one. Please take a look at the photo below.

2.1. With 100k vertices and 99,999 edges are randomly generated beforehand, there would be some edges causing cycles (for example: 2-->3 and 3-->2 as in the photo example). So we will not use these edges to construct the DAG. As a result, the result of DAG would have <= 100k vertices and <= 99,999 edges because we did not use all edges to construct the DAG to avoid cycles.

And the DAG might have many disconnected components as the Output 1 in the example we sent. So our duty is to adding some more edges (out of the 99,999 randomly generated that we have beforehand) to connect these disconnected components right? And finally, no matter what edges we add to construct the DAG, the final and complete DAG must have EXACT 100k vertices and 99,999 edges. No more no less. Right? Or we don’t care about the number of vertices and edges of the complete DAG?

2.2. “Recall however topological orders are not unique; you are expected to ensure the order is unique and consitent when vertices and edges are inserted in any order” but the final-complete DAG must be singly unique as in the problem description _“Hence, no matter what insertion order vertices are added to the graph, after calling Insert(vertex) on all vertices,
the DAG must converge to becoming the singly unique instance of a complete DAG.” Right?
So our duty is to setup a rule, to add more edges to connect the disconnected components after all, which is to ensure the order is unique and consistent when vertices and edges are inserted in any order

To be clear, take the Output 2 (in the photo) as an example:
From Output 1 to Output 2, we have many ways to connect the 2 disconnected components. If we connect 1-->4 instead of 3-->4 (as we did in the Output 2), we will the Output 3 which is still correct. So the rule is defined by ourselves to connect them and make sure the final-complete DAG is singly unique in any insertion order of vertices and edges.