Avengers (Editorial)

According to the problem statement, it is impossible to return to the starting city after traveling along several roads, so the road graph is a directed acyclic graph.

The task is to find three distinct vertices such that no path passes through all of them, or to report that no such vertices exist.

If n < 3, it is impossible to choose three distinct cities, and the answer is $-1$. From now on, we assume that n \ge 3.

Any path in an acyclic graph visits vertices in the order of their topological sort. Therefore, if a path contains vertices $x$ and $y$, then one of them is reachable from the other. This leads to the key observation: if there exist two vertices $x$ and $y$ such that neither is reachable from the other, then no path passes through both of them. Consequently, there is no path through the triple x, y, z either, where $z$ is an arbitrary third vertex.

Such a pair of vertices can be conveniently found using Kahn's topological sorting algorithm. Initially, all vertices with zero in-degree are placed into the queue. Then vertices are extracted from the queue one by one and removed from the graph together with their outgoing edges; vertices whose in-degree becomes zero as a result are added to the queue.

Statement 1. If at some moment the queue simultaneously contains two vertices $x$ and $y$, then there is no path between them.

Statement 2. If at every step of the algorithm the queue contains exactly one vertex, then all vertices of the graph lie on a single path.

Thus, the algorithm is as follows: run Kahn's algorithm and check the size of the queue before each extraction. As soon as it contains more than one vertex, take any two of them as $x$ and $y$, and any other vertex of the graph as $z$. If this moment never occurs, print $-1$.

Each vertex and each edge is processed at most once, so the time complexity of the algorithm is O(n + m), and the memory usage is O(n + m).

Example

The graphs from the sample tests have the following structure:

• In the first example, the queue contains a single vertex at every step: \{1\}, \{2\}, \{3\}. The graph contains the path 1 \to 2 \to 3 passing through all vertices, so the answer is $-1$.

• In the second example, the queue initially contains vertex $1$. After it is removed, the in-degrees of vertices $2$ and $3$ become zero, and both of them appear in the queue simultaneously. There is no path between vertices $2$ and $3$, so we can take x = 2, y = 3 and z = 1 as the answer.

Algorithm implementation

Declare the data structures. The input graph is represented by the adjacency list $g$, and the in-degrees of the vertices are stored in the array InDegree.

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

Read the input data.

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);

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

  InDegree[b]++;
}

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

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

The three desired vertices are stored in the variables $x,y$ and $z$.

x = y = -1;

Continue executing the algorithm as long as the queue $q$ is not empty.

while (!q.empty())
{

If the queue contains more than one vertex at the same time, this means that the solution has been found.

  if (q.size() > 1)
  {
    x = q[0];
    y = q[1];
    break;
  }

Extract the vertex $v$ from the queue — it will become the current vertex in the topological order.

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

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

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

Kahn's algorithm is complete. If the value of $x$ is still $-1$, this means that no solution exists.

if (x == -1)
  printf("-1\n");
else
{

If a solution exists, choose $z$ as the smallest vertex different from $x$ and $y$.

  z = 1;
  while (z == x || z == y) z++;
    printf("%d %d %d\n", x, y, z);
}