Remove Directed Edges
Contest: Codeforces Round 786 (Div. 3)
Difficulty rating: 2000
Tags: dfs and similar, dp, graphs

You are given a directed acyclic graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$. There are no multiple edges and self-loops.

Let $$$\mathit{in}_v$$$ be the number of incoming edges (indegree) and $$$\mathit{out}_v$$$ be the number of outgoing edges (outdegree) of vertex $$$v$$$.

You are asked to remove some edges from the graph. Let the new degrees be $$$\mathit{in'}_v$$$ and $$$\mathit{out'}_v$$$.

You are only allowed to remove the edges if the following conditions hold for every vertex $$$v$$$:

- $$$\mathit{in'}_v < \mathit{in}_v$$$ or $$$\mathit{in'}_v = \mathit{in}_v = 0$$$;
- $$$\mathit{out'}_v < \mathit{out}_v$$$ or $$$\mathit{out'}_v = \mathit{out}_v = 0$$$.

Let's call a set of vertices $$$S$$$ cute if for each pair of vertices $$$v$$$ and $$$u$$$ ($$$v \neq u$$$) such that $$$v \in S$$$ and $$$u \in S$$$, there exists a path either from $$$v$$$ to $$$u$$$ or from $$$u$$$ to $$$v$$$ over the non-removed edges.

What is the maximum possible size of a cute set $$$S$$$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $$$0$$$?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges of the graph.

Each of the next $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) — the description of an edge.

The given edges form a valid directed acyclic graph. There are no multiple edges.

Output format:
Print a single integer — the maximum possible size of a cute set $$$S$$$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $$$0$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can remove edges $$$(1, 2)$$$ and $$$(2, 3)$$$. $$$\mathit{in} = [0, 1, 2]$$$, $$$\mathit{out} = [2, 1, 0]$$$. $$$\mathit{in'} = [0, 0, 1]$$$, $$$\mathit{out'} = [1, 0, 0]$$$. You can see that for all $$$v$$$ the conditions hold. The maximum cute set $$$S$$$ is formed by vertices $$$1$$$ and $$$3$$$. They are still connected directly by an edge, so there is a path between them.

In the second example, there are no edges. Since all $$$\mathit{in}_v$$$ and $$$\mathit{out}_v$$$ are equal to $$$0$$$, leaving a graph with zero edges is allowed. There are $$$5$$$ cute sets, each contains a single vertex. Thus, the maximum size is $$$1$$$.

In the third example, you can remove edges $$$(7, 1)$$$, $$$(2, 4)$$$, $$$(1, 3)$$$ and $$$(6, 2)$$$. The maximum cute set will be $$$S = \{7, 3, 2\}$$$. You can remove edge $$$(7, 3)$$$ as well, and the answer won't change.

Here is the picture of the graph from the third example:

Example input:
3 3
1 2
2 3
1 3

Example output:
2

Example input:
5 0

Example output:
1

Editorial:
Let's solve the problem in reverse.
Imagine we have already removed some edges, so that the conditions hold. When is some set of vertices considered cute? Since the graph is acyclic, we can topologically sort the vertices in the set. The vertices are reachable from each other, so there exists a path from the $$$i$$$-th vertex in the set to the $$$(i+1)$$$-st vertex. Thus, there exists a path that goes through all chosen vertices.
However, we can make this conclusion even stronger. In the optimal answer, not just the path goes from the $$$i$$$-th vertex to the $$$(i+1)$$$-st one, but a single edge. That can be shown by contradiction. Let there be some vertices $$$v$$$ and $$$u$$$ that are adjacent in the chosen cute set. There exists a path between them, but not a single edge. We want to show that this set is not optimal and can be made larger.
The vertices on that path don't belong to the set. If they did, they would be between $$$v$$$ and $$$u$$$ in the set (because of the topological order). We can add them to the set. Every vertex that can reach $$$v$$$, can reach them too, and every vertex that can be reached from $$$u$$$, can be reached from them. Thus, it will still be a cute set. Now every vertex from $$$v$$$ to $$$u$$$ has an edge between them and the size of the set is larger.
Thus, we showed that the maximum set in the answer is always some path in the graph.
So the task is to choose some path, then remove some edges so that this path still exists and the conditions hold. Note that if the conditions hold for some set of remaining edges, then we can remove any edge from it, and the conditions will still be met. Thus, we can only leave this path.
Let's look closer into the conditions. What they actually tell is the following. If a vertex has incoming edges, then remove at least one of them. The same for the outgoing edges.
Since we are looking for a path, it's enough to leave one outgoing edge for all vertices except the last one and leave one incoming edge for all vertices except the first one.
In order to achieve that, every vertex except the last one should have at least two outgoing edges and every vertex except the first one should have at least two incoming edges.
We can see that this condition is not only necessary, but sufficient as well. Just remove the outgoing edges which don't go to the next vertex and the incoming edges which don't go from the previous vertex.
Now we can wrap this up into the dynamic programming. Initialize the answer with $$$1$$$, since you can always remove all edges, and get a set with one vertex.
Then let $$$\mathit{dp}_v$$$ be the longest path such that it starts in vertex $$$v$$$, all vertices in it have at least two incoming edges and all vertices except maybe the final one have at least two outgoing edges.
Initialize the $$$\mathit{dp}$$$ for the vertices that can be the final in the path (have at least two incoming edges) with $$$1$$$. Then update $$$\mathit{dp}_v$$$ for all $$$v$$$ that can be internal vertices (have at least two outgoing and two incoming edges) with $$$\mathit{dp}_u + 1$$$ for all outgoing edges $$$(v, u)$$$.
Finally, update the answer from the vertices that can be the first one in the path. For each vertex $$$v$$$ that has at least two outgoing edges, take the value of $$$\mathit{dp}_u + 1$$$ for all outgoing edges $$$(v, u)$$$.
Overall complexity: $$$O(n + m)$$$.