Official Analysis (Java)

Explanation

We want to find the number of pairs of cows for which crossing at least one road is necessary for one cow to visit the other.

Let's consider an arbitrary cow. By performing either BFS or DFS, we can determine which squares that cow can reach without crossing any roads. Then, we can determine which cows cannot be visited without crossing any roads by checking if that cow's square is reachable.

Finally, to determine all such pairs of cows, we can perform BFS or DFS for each cow and compute the number of unreachable cows, making sure to avoid double-counting pairs.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
from typing import List, Tuple


def neighbors(r: int, c: int) -> List[Tuple[int, int]]:
	""":return: the 4 cardinal neighbors of a position"""
	return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]


with open("countcross.in") as read:
	side_len, cow_num, road_num = [int(i) for i in read.readline().split()]