{
Solution for task NET
-------- --- ---- ---
The network of schools can be represented by a directed graph whose vertices
are the schools and (A, B) is an edge in the graph iff school B is in the
distribution list of school A. Let us first reformulate the task using graph
terminology.
We use the notation p->q if there is a (directed) path from p to q in a graph.
A set of vertices D of a graph G is called dominator set of G if for each
vertex q there is a vertex p in D such that p->q.
Subtask A is to find a dominator set of G with minimal number of elements.
A set of vertices CD of G is called codominator set of G if for each vertex p
there is a vertex q in CD such that p->q. A graph G is called strongly
connected, if for all vertices p and q there is a path p->q and a path q->p
in G.
Solution of subtask B is the minimal number of new edges that are necessary
to make G strongly connected.
Let us denote the number of elements of a set S by |S|.
Let D be a minimal dominator set and CD be a minimal codominator set of G.
We shall prove that solution of subtask B is 0 if G is strongly connected,
and Max(|D|, |CD|) otherwise.
The proof follows from the statements S1 and S2.
We can assume without loss of generality that |D|<=|CD|.
S1. If D is a one element set containing p and CD contains the elements
q1,...,qk then introducing the new edges (q1, p), ... , (qk, p) makes G
strongly connected.
Proof: Let u,v be arbitrary vertices of G. Then there is an element qi in
CD such that u->qi, therefore u->qi->p->v is a path from u to v.
S2. If |D|>1 then there are vertices p in D and q in CD such that introducing
the new edge (q, p) in G makes D-[p] a new dominator set and CD-[q] a new
codominator set of G.
Proof: Since |D|>1 there are different vertices p1 and p2 in D, and there
are different vertices q1 and q2 in CD such that p1->q1 and p2->q2. Then
the new edge (p,q) will be (q1,p2). Indeed, any vertex u that was
reachable from p2 by the path p2->u will be reachable from p1 by
p1->q1->p2->u and for any path v->q1 there will be a path v->q1->p2->q2
in the new graph.
It is obvious that a codominator set of a graph G is a dominator set of the
transposed graph GT and conversely. Therefore we can compute the minimal
codominator set of G by transposing 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 that is produced by this algorithm is a dominator set.
Assume that D contains the vertices p1,...,pk and D is not minimal, i.e.
there is a minimal dominator set Q that contains vertices q1,...ql, and lqi. But every vertex is reachable from Q, therefore pk is also
reachable from some vertex in Q, say qi->pk. We obtained that there is a path
pi->qi->pk from pi to pk. The algorithm has executed both Search(pi) and
Search(pk). Either Search(pi) or Search(pk) was executed first, the vertex
pk was excluded from D because pk is reachable from pi. This contradicts to
the assumption that D is not minimal.
The algorithm above can be modified to avoid set operations union (+) and
difference (-). Indeed, when Search(p) is executed, we can include p in the
set Dominated and exclude p from D.
}
Program Net;
Const
MaxN=200; { max number of schools }
Type
GraphType=Array[1..MaxN,0..MaxN] Of 0..MaxN;
VertexSet=Set Of 1..MaxN;
Var
OutFile: Text;
N :Word; { the number of schools }
G: GraphType; { representation of the network with graph G; }
{ G[p,0] is the number of edges outgoing from p }
{ the outgoing edges from p: (p, G[p,i]) 1<=i<=G[p,0]) }
Domin, { dominator set }
CoDomin: VertexSet; { codominator set }
NoDomins, { number of dominator elements }
NoCoDomins: 0..MaxN;{ number of codominator elements }
AnswerB: 0..MaxN; { solution of subtask B }
p: 0..MaxN;
Procedure ReadInput;
{ Global output variables: N, G }
Var InFile: Text;
i,p: Word;
Begin
Assign(InFile, 'input.txt'); Reset(InFile);
ReadLn(InFile,N);
For i:=1 To N Do
G[i,0]:=0;
For i:=1 To N Do Begin
Read(InFile, p);
While p<>0 Do Begin
Inc(G[i,0]);
G[i,G[i,0]]:=p;
Read(InFile, p);
End;
ReadLn(InFile);
End;
Close(InFile);
End { ReadInput };
Procedure ComputeDomin(Const G: GraphType; Var D: VertexSet);
{ Computes a minimal dominator set D of graph G }
{ Global input variables: N }
Var
Dominated, Reachable: Set of 1..MaxN;
p: 1..MaxN;
Procedure Search(p:Word);
Var i: Word;
Begin
Exclude(D, p);
Include(Dominated, p);
For i:= 1 To G[p,0] Do
If Not (G[p,i] in Reachable) Then Begin
Include(Reachable,G[p,i]);
Search(G[p,i]);
End;
End { Search };
Begin { ComputeDomin }
D:=[];
Dominated:=[];
For p:=1 To N Do
If Not (p In Dominated) Then Begin
Reachable:=[p];
Search(p);
Include(D, p);
End;
End { ComputeDomin };
Procedure ComputeCoDomin(Const G: GraphType; Var CD: VertexSet);
{ Computes a minimal codominator set D of graph G }
{ Global input variables: N }
Var
GT: GraphType; { transposed graph of G }
p,q: 1..MaxN; i:Word;
Begin { ComputeCoDomin }
For p:=1 To N Do
GT[p,0]:=0;
For p:=1 To N Do { compute the transpose of the graph G in GT }
For i:=1 To G[p,0] Do Begin
q:=G[p,i];
Inc(GT[q,0]); GT[q,GT[q,0]]:=p;
End;
ComputeDomin(GT, CD) { computes CD, the dominator set of GT }
End;{ ComputeCoDomin }
Begin { Program }
ReadInput;
ComputeDomin(G,Domin);
ComputeCoDomin(G,CoDomin);
NoDomins:=0;
For p:=1 To N Do { count the number of elements in the set Domin }
If p In Domin Then Inc(NoDomins);
NoCoDomins:=0;
For p:=1 To N Do { count the number of elements in the set CoDomin }
If p In CoDomin Then Inc(NoCoDomins);
If (Domin=[1]) And (CoDomin=[1]) { strongly connected }
Then AnswerB:=0
Else If NoDomins > NoCoDomins
Then AnswerB:=NoDomins
Else AnswerB:=NoCoDomins;
Assign(OutFile, 'output.txt'); Rewrite(OutFile);
WriteLn(OutFile, NoDomins);
Writeln(OutFile, AnswerB);
Close(OutFile);
End.
{ Scientific Committee IOI'96 }