The Unique Topological Sort (Editorial)

We use Kahn's algorithm. Recall that it maintains a queue of vertices with zero in-degree – exactly the vertices that can be placed in the next position of the topological sort. At each iteration, a vertex is extracted from the queue and appended to the answer, and the in-degrees of all its neighbors are decreased by $1$. Vertices whose in-degree becomes zero are added to the queue.

Key observation: the topological sort is unique if and only if the queue contains exactly one vertex before each extraction.

Complexity. Each vertex and each edge is processed once, so the running time is O(n + m).

Example

The graphs from the test cases are as follows:

In the first sample the topological sort is unique:

• $1,2,3$.

In the second sample there are two possible topological sorts:

• $1,2,3$;

• $1,3,2$;

Algorithm implementation

Store the input graph in an adjacency list $g$. The in-degrees of the vertices are stored in the array InDegree. Declare the queue $q$.

vector<vector<int> > g;
vector<int> InDegree;
deque<int> q;

Read the input graph. For each edge $(a,b)$ increment InDegree[b] by $1$.

scanf("%d %d", &n, &m);
g.resize(n + 1);
InDegree.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  InDegree[b]++;
}

All vertices with an in-degree of zero add to the queue $q$.

for (i = 1; i < InDegree.size(); i++)
  if (!InDegree[i]) q.push_back(i);

Set flag = 1 if the topological sort is unique.

flag = 1;

Continue the algorithm while the queue $q$ is not empty.

while (!q.empty())
{

If the queue contains more than one vertex, then the topological sort is not unique.

  if (q.size() > 1) flag = 0;

Pop the current vertex $v$ from the queue.

  v = q.front(); q.pop_front();

Remove the edges (v, to) from the graph. For each such edge, decrease the in-degree of vertex $to$. If the in-degree of vertex $to$ becomes zero, add it to the queue.

  for (int to : g[v])
  {
    InDegree[to]--;
    if (!InDegree[to]) q.push_back(to);
  }
}

Depending on the value of $flag$, print the answer.

if (flag == 1)
  printf("YES\n");
else
  printf("NO\n");