Editorial for IOI '96 P3 - Network of Schools

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The network of schools can be represented by a directed graph whose vertices are the schools and $(A, B)$ ~(A, B)~ is an edge in the graph iff school $B$ ~B~ is in the distribution list of school $A$ ~A~. Let us first reformulate the task using graph terminology.

We use the notation $p \to q$ ~p \to q~ if there is a (directed) path from $p$ ~p~ to $q$ ~q~ in a graph. A set of vertices $D$ ~D~ of a graph $G$ ~G~ is called dominator set of $G$ ~G~ if for each vertex $q$ ~q~ there is a vertex $p$ ~p~ in $D$ ~D~ such that $p \to q$ ~p \to q~.

Subtask A is to find a dominator set of $G$ ~G~ with minimal number of elements. A set of vertices $CD$ ~CD~ of $G$ ~G~ is called codominator set of $G$ ~G~ if for each vertex $p$ ~p~ there is a vertex $q$ ~q~ in $CD$ ~CD~ such that $p \to q$ ~p \to q~. A graph $G$ ~G~ is called strongly connected, if for all vertices $p$ ~p~ and $q$ ~q~ there is a path $p \to q$ ~p \to q~ and a path $q \to p$ ~q \to p~ in $G$ ~G~.

Solution of subtask B is the minimal number of new edges that are necessary to make $G$ ~G~ strongly connected.

Let us denote the number of elements of a set $S$ ~S~ by $|S|$ ~|S|~.

Let $D$ ~D~ be a minimal dominator set and $CD$ ~CD~ be a minimal codominator set of $G$ ~G~.

We shall prove that solution of subtask B is $0$ ~0~ if $G$ ~G~ is strongly connected, and $\max(|D|, |CD|)$ ~\max(|D|, |CD|)~ otherwise.

The proof follows from statements 1 and 2. We can assume without loss of generality that $|D| \le |CD|$ ~|D| \le |CD|~.

If $D$ ~D~ is a one-element set containing $p$ ~p~ and $CD$ ~CD~ contains the elements $q_1, \dots, q_k$ ~q_1, \dots, q_k~ then introducing the new edges $(q_1, p), \dots, (q_k, p)$ ~(q_1, p), \dots, (q_k, p)~ makes $G$ ~G~ strongly connected.

Proof: Let $u$ ~u~, $v$ ~v~ be arbitrary vertices of $G$ ~G~. Then there is an element $q_i$ ~q_i~ in $CD$ ~CD~ such that $u \to q_i$ ~u \to q_i~, therefore $u \to q_i \to p \to v$ ~u \to q_i \to p \to v~ is a path from $u$ ~u~ to $v$ ~v~.
If $|D| > 1$ ~|D| > 1~ then there are vertices $p$ ~p~ in $D$ ~D~ and $q$ ~q~ in $CD$ ~CD~ such that introducing the new edge $(q, p)$ ~(q, p)~ in $G$ ~G~ makes $D-[p]$ ~D-[p]~ a new dominator set and $CD-[q]$ ~CD-[q]~ a new codominator set of $G$ ~G~.

Proof: Since $|D| > 1$ ~|D| > 1~ there are different vertices $p_1$ ~p_1~ and $p_2$ ~p_2~ in $D$ ~D~, and there are different vertices $q_1$ ~q_1~ and $q_2$ ~q_2~ in $CD$ ~CD~ such that $p_1 \to q_1$ ~p_1 \to q_1~ and $p_2 \to q_2$ ~p_2 \to q_2~. Then the new edge $(p, q)$ ~(p, q)~ will be $(q_1, p_2)$ ~(q_1, p_2)~. Indeed, any vertex $u$ ~u~ that was reachable from $p_2$ ~p_2~ by the path $p_2 \to u$ ~p_2 \to u~ will be reachable from $p_1$ ~p_1~ by $p_1 \to q_1 \to p_2 \to u$ ~p_1 \to q_1 \to p_2 \to u~ and for any path $v \to q_1$ ~v \to q_1~ there will be a path $v \to q_1 \to p_2 \to q_2$ ~v \to q_1 \to p_2 \to q_2~ in the new graph.

It is obvious that a codominator set of a graph $G$ ~G~ is a dominator set of the transposed graph $G^T$ ~G^T~ and conversely. Therefore we can compute the minimal codominator set of $G$ ~G~ by transposing $G$ ~G~ and then computing the minimal dominator set of the transposed graph.

The strategy for computing a minimal dominator set is the following. (We use Pascal terminology for set operations)

Dominated:=[];
D:=[];
While there is a p not in Dominated Do Begin
  Search(p);(* put all vertices in set Reachable that are reachable from p*)
  Dominated:=Dominated+Reachable;
  D:=D-Reachable; (* exclude all elements of D that are in Reachable *)
  Include p in D;
End;

Evidently, the set $D$ ~D~ that is produced by this algorithm is a dominator set. Assume that $D$ ~D~ contains the vertices $p_1, \dots, p_k$ ~p_1, \dots, p_k~ and $D$ ~D~ is not minimal, i.e. there is a minimal dominator set $Q$ ~Q~ that contains vertices $q_1, \dots, q_l$ ~q_1, \dots, q_l~, and $l < k$ ~l < k~. Since $D$ ~D~ is a dominator set and $Q$ ~Q~ is a minimal dominator set, it follows that for each $q_i$ ~q_i~ in $Q$ ~Q~ there is a unique $p_i$ ~p_i~ in $D$ ~D~ such that $q_i$ ~q_i~ is reachable from $p_i$ ~p_i~ by a path $p_i \to q_i$ ~p_i \to q_i~. But every vertex is reachable from $Q$ ~Q~, therefore $p_k$ ~p_k~ is also reachable from some vertex in $Q$ ~Q~, say $q_i \to p_k$ ~q_i \to p_k~. We obtained that there is a path $p_i \to q_i \to p_k$ ~p_i \to q_i \to p_k~ from $p_i$ ~p_i~ to $p_k$ ~p_k~. The algorithm has executed both $Search(p_i)$ ~Search(p_i)~ and $Search(p_k)$ ~Search(p_k)~. Either $Search(p_i)$ ~Search(p_i)~ or $Search(p_k)$ ~Search(p_k)~ was executed first, the vertex $p_k$ ~p_k~ was excluded from $D$ ~D~ because $p_k$ ~p_k~ is reachable from $p_i$ ~p_i~. This contradicts the assumption that $D$ ~D~ is not minimal.

The algorithm above can be modified to avoid set operations union (+) and difference (-). Indeed, when $Search(p)$ ~Search(p)~ is executed, we can include $p$ ~p~ in the set Dominated and exclude $p$ ~p~ from $D$ ~D~.

Comments

There are no comments at the moment.