Skip to content

Latest commit

 

History

History
23 lines (13 loc) · 2.76 KB

Ethnographers Births and Deaths.md

File metadata and controls

23 lines (13 loc) · 2.76 KB
Raw

Algorithm

We will create a bipartite graph with 2n vertices. Each vertex represents an event. For 1 ≤ i ≤ n, let vertex Bi represent the birth of Pi, and let vertex Di represent the death of Pi. A directed edge from an arbitrary vertex u to an arbitrary vertex v indicates that the event represented by vertex u precedes the event represented by vertex v.

We will draw an initial n edges: For 1 ≤ i ≤ n, we will draw a directed edge from Bi to Di. This represents the necessity that a person must be born before that person can die (and we are told that everyone is deceased).

Now we will loop through the facts. Each fact can be represented by 1 or 2 directed edges.

  • Each fact of the form "For some i and j, person Pi died before person Pj was born," can be represented as a directed edge from Di to Bj.
  • Each fact of the form "For some i and j, the life spans of Pi and Pj overlapped at least partially," can be represented by 2 directed edges. One directed edge will be from Bi to Dj, and another directed edge will be from Bj to Di

Lemma: A directed graph has a cycle if and only if it has a "back-edge".

To determine if the facts are consistent, all we have to do is determine whether our graph (lets call it G) has a cycle. For a directed connected graph, we could simply run DFS on the graph. Using our lemma above, if there are any back-edges, then the graph has a cycle. However, our graph G is not necessarily connected, and we want DFS to visit all 2n nodes. To achieve this, we will have to run DFSall (which is basically just running DFS from every node) to ensure all 2n nodes are visited. If a back-edge exists, then G has a cycle. If a back-edge does not exist, then G does not have a cycle.

Notice that if G has a cycle, then each vertex that represents an event must precede another event in the cycle. But this is impossible. Each vertex/event in the cycle has an incoming arrow, so there is no vertex/event that could have possibly occurred first. So we can conclude that the facts are inconsistent.

If it is the case that G does not have a cycle, then G is a DAG. We can topological sort the DAG to provide an ordering that does not have any inconsistencies. This ordering will be consistent with the presented facts.

Time/Space Complexity

  • Time Complexity: O(n + m) due to DFS.
  • Space Complexity: O(n + m) since we create a graph.