188 lines
6.7 KiB
ObjectPascal
188 lines
6.7 KiB
ObjectPascal
{
|
|
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 l<k.
|
|
Since D is a dominator set and Q is a minimal dominator set it follows that
|
|
for each qi in Q there is a unique pi in D such that qi is reachable from pi
|
|
by a path pi->qi. 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 } |