P17459 [GESP202609 Level 7] Mandatory Nodes

Given a directed graph $G$ with $n$ nodes and $m$ edges, the nodes in $G$ are numbered $1,2,\ldots,n$ in order. The $i$-th edge ($1\le i\le m$) goes from node $u_i$ to node $v_i$. Any node in $G$ with in-degree $0$ can be a valid starting node, and any node with out-degree $0$ can be a valid ending node. If all possible paths in $G$ from any valid starting node to any valid ending node must pass through node $u$, then $u$ is called a mandatory node. Note that a mandatory node can be a valid starting node or a valid ending node. Please find the indices of all mandatory nodes in $G$. For example, in the figure below, the valid starting nodes are node $1$ and node $2$, and the valid ending nodes are node $7$ and node $8$. ```text (1) (5)---->(7) \ ^ \ ^ v / v / (3) / (6) ^ \ / \ / v / v (2)---->(4) (8) ``` All paths from valid starting nodes to valid ending nodes are: - $1\to 3\to 4\to 5\to 7$ - $1\to 3\to 4\to 5\to 6\to 7$ - $1\to 3\to 4\to 5\to 6\to 8$ - $2\to 3\to 4\to 5\to 7$ - $2\to 3\to 4\to 5\to 6\to 7$ - $2\to 3\to 4\to 5\to 6\to 8$ - $2\to 4\to 5\to 7$ - $2\to 4\to 5\to 6\to 7$ - $2\to 4\to 5\to 6\to 8$ Therefore, there are two mandatory nodes, with indices $4,5$.

The first line contains two positive integers $n,m$, representing the number of nodes and the number of edges in the directed graph $G$. The next $m$ lines each contain two positive integers $u_i,v_i$, representing a directed edge from node $u_i$ to node $v_i$. It is guaranteed that $G$ has at least one valid starting node and at least one valid ending node, and that there is at least one path from a valid starting node to a valid ending node. Also, there are no isolated nodes (i.e., nodes whose out-degree and in-degree are both $0$).

The first line contains an integer, representing the number of mandatory nodes $k$. If mandatory nodes exist, then the second line outputs the indices of all mandatory nodes in $G$ in increasing order.

For $40\%$ of the test points, it is guaranteed that $1\le n\le 100$ and $1\le m\le 200$. For all test points, it is guaranteed that $1\le n\le 1000$ and $1\le m\le 2000$. It is guaranteed that $G$ has at least one valid starting node and at least one valid ending node, and that there is at least one path from a valid starting node to a valid ending node. Also, there are no isolated nodes (i.e., nodes whose out-degree and in-degree are both $0$). Translated by ChatGPT 5