Upgrading Cities
Contest: Codeforces Round 520 (Div. 2)
Difficulty rating: 2900
Tags: dfs and similar, graphs

There are $$$n$$$ cities in the kingdom $$$X$$$, numbered from $$$1$$$ through $$$n$$$. People travel between cities by some one-way roads. As a passenger, JATC finds it weird that from any city $$$u$$$, he can't start a trip in it and then return back to it using the roads of the kingdom. That is, the kingdom can be viewed as an acyclic graph.

Being annoyed by the traveling system, JATC decides to meet the king and ask him to do something. In response, the king says that he will upgrade some cities to make it easier to travel. Because of the budget, the king will only upgrade those cities that are important or semi-important. A city $$$u$$$ is called important if for every city $$$v \neq u$$$, there is either a path from $$$u$$$ to $$$v$$$ or a path from $$$v$$$ to $$$u$$$. A city $$$u$$$ is called semi-important if it is not important and we can destroy exactly one city $$$v \neq u$$$ so that $$$u$$$ becomes important.

The king will start to act as soon as he finds out all those cities. Please help him to speed up the process.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$1 \le m \le 300\,000$$$) — the number of cities and the number of one-way roads.

Next $$$m$$$ lines describe the road system of the kingdom. Each of them contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting one-way road from $$$u_i$$$ to $$$v_i$$$.

It is guaranteed, that the kingdoms' roads make an acyclic graph, which doesn't contain multiple edges and self-loops.

Output format:
Print a single integer — the number of cities that the king has to upgrade.

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

Note:
In the first example:

- Starting at the city $$$1$$$ we can reach all the other cities, except for the city $$$6$$$. Also, from the city $$$6$$$ we cannot reach the city $$$1$$$. Therefore, if we destroy the city $$$6$$$ then the city $$$1$$$ will become important. So $$$1$$$ is a semi-important city.
- For city $$$2$$$, the set of cities that cannot reach $$$2$$$ and cannot be reached by $$$2$$$ is $$$\{6\}$$$. Therefore, destroying city $$$6$$$ will make the city $$$2$$$ important. So city $$$2$$$ is also semi-important.
- For city $$$3$$$, the set is $$$\{5, 6\}$$$. As you can see, destroying either city $$$5$$$ or $$$6$$$ will not make the city $$$3$$$ important. Therefore, it is neither important nor semi-important.
- For city $$$4$$$, the set is empty. So $$$4$$$ is an important city.
- The set for city $$$5$$$ is $$$\{3, 6\}$$$ and the set for city $$$6$$$ is $$$\{3, 5\}$$$. Similarly to city $$$3$$$, both of them are not important nor semi-important.
- The city $$$7$$$ is important since we can reach it from all other cities.

In the second example, the important cities are $$$1$$$ and $$$4$$$. The semi-important cities are $$$2$$$ and $$$3$$$.

Example input:
7 7
1 2
2 3
3 4
4 7
2 5
5 4
6 4

Example output:
4

Example input:
6 7
1 2
2 3
3 4
1 5
5 3
2 6
6 4

Example output:
4

Editorial:
The main idea of this problem is to calculate $$$in_u$$$ and $$$out_u$$$ for every node $$$u$$$, where $$$in_u$$$ denotes the number of nodes that can reach $$$u$$$ and $$$out_u$$$ denotes the number of nodes that can be reached by $$$u$$$. If $$$in_u+out_u=N+1$$$ then $$$u$$$ is important or $$$N$$$ if $$$u$$$ is semi-important.
However, it may not possible to calculate $$$in_u$$$ and $$$out_u$$$ for every node $$$u$$$ in given time (please tell me if it's possible) so we have to do some tricks.
First of all, we need to find an arbitrary longest path ($$$P$$$)$$$=s_1 \rightarrow s_2 \rightarrow... \rightarrow s_k$$$ on the graph ($$$k$$$ is the number of nodes on this path). If a node is important then it must lie on this path ($$$1$$$). Proof: Assume there is a node $$$u$$$ that is important and doesn't lie on ($$$P$$$). Let $$$s_i$$$ be the rightmost node on ($$$P$$$) and can reach $$$u$$$. It's true that $$$i < k$$$, because if $$$i=k$$$ then we have a longer path than the one we found so it's not possible. By definition of $$$i$$$, $$$s_{i+1}$$$ cannot reach $$$u$$$. Therefore $$$u$$$ must be able to reach $$$s_{i+1}$$$ (because $$$u$$$ is important). This leads to a conflict: We have a path that is longer than the one we found: $$$s_1 \rightarrow s_2 \rightarrow \dots \rightarrow s_i \rightarrow u \rightarrow s_{i+1} \rightarrow \dots \rightarrow s_k$$$. Therefore statement ($$$1$$$) is proved.
It takes $$$O(N+M)$$$ to find ($$$P$$$).
Let's deal with important nodes first. Because all important nodes lie on the path ($$$P$$$) so it makes no sense to calculate $$$in$$$ and $$$out$$$ for those nodes that don't belong to ($$$P$$$). We can calculate $$$out$$$ by iterate through $$$P$$$ from $$$s_k$$$ to $$$s_1$$$. At each node $$$s_i$$$, we just need to use bfs or dfs to search for the nodes that can be reached by $$$s_i$$$. Because we visit each node $$$1$$$ time then it takes $$$O(N+M)$$$ to do this. To calculate $$$in$$$ we just need to reverse the direction of the edges and do similarly.
Now we need to find the semi nodes. There are two types of semi nodes: those belong to ($$$P$$$) and those don't. For the ones belong to ($$$P$$$), we just need to check if $$$in_u+out_u=N$$$. For the ones don't belong to ($$$P$$$), suppose we are dealing with node $$$u$$$. Let $$$s_i$$$ be the rightmost node on ($$$P$$$) that can reach $$$u$$$ and $$$s_j$$$ be the leftmost node on ($$$P$$$) that can be reached by $$$u$$$. It's obvious that $$$i<j-1$$$. Let $$$L_u=i$$$ and $$$R_u=j$$$, let $$$leng$$$ equal $$$j-i-1$$$. If $$$leng>1$$$ then u is not a semi node (because we have to delete all nodes between i and j not inclusive), or else we must erase $$$s_{i+1}$$$ to make $$$u$$$ a semi important node. We can see that the path from $$$s_i$$$ to $$$u$$$ contains only $$$s_i$$$ and $$$u$$$, and the path from $$$u$$$ to $$$s_j$$$ contains only $$$u$$$ and $$$s_j$$$, because otherwise there exists a longer path than ($$$P$$$), which is false. So we consider $$$u$$$ as a candidate. Moreover, if exists a node $$$v$$$ that is a candidate and $$$L_u=L_v$$$ (also leads to $$$R_u=R_v$$$) then both $$$u$$$ and $$$v$$$ are not semi important nodes. Proof: After we delete $$$s_{i+1}$$$, for $$$u$$$, exists a path that is as long as ($$$P$$$) and does not go through $$$u$$$ (it goes through $$$v$$$) so $$$u$$$ is not a important node, based on statement ($$$1$$$). Same for $$$v$$$. Briefly, at this point we have the path ($$$P$$$) and a list of nodes $$$u_1, u_2, ..., u_t$$$. For every $$$i$$$, $$$u_i$$$ is a candidate and $$$L_{ui}+1=R_{ui}-1$$$. For every $$$i$$$, $$$j$$$, $$$L_{ui}!=L_{uj}$$$.
So now we are going to calculate $$$in$$$ and $$$out$$$ for those candidate nodes. We can do this similarly as when we find the important nodes. To calculate $$$out$$$, iterate through $$$s_k$$$ to $$$s_1$$$. At each node $$$s_i$$$, bfs or dfs to search for nodes that can be reached by $$$s_i$$$. Additionally, if there is a candidate node $$$v$$$ that $$$R_v=i-1$$$, we start a search from $$$v$$$ to find those nodes that can be reached by $$$v$$$, we have $$$out_v=out_{si}+$$$ the number of nodes we just found. After that we pop those nodes from the stack (or whatever), mark them as not visited and continue to iterate to $$$s_{i-1}$$$. To calculate $$$in$$$ we reverse the directs of the edges and do the same. Because each node is visited $$$1$$$ time by nodes on ($$$P$$$) and at most $$$2$$$ times by candidate nodes so it takes $$$O(3(N+M))$$$.
The total complexity is $$$O(N+M)$$$.