Given a directed graph G V E G is said to contain perfect c

Given a directed graph G = (V, E), G is said to contain perfect cycles if there is a collection of node-disjoint cycles such that every node in V belongs to a cycle. Describe and analyze an efficient algorithm to find perfect cycles for a given graph, or correctly report that no perfect cycles exist.

Solution

CIRCUIT-FINDING ALGORITHM

begin
integer list array A(n), B(n); logical array blocked (n); integer s;

logical procedure CIRCUIT (integer value v);

begin logical f;

procedure UNBLOCK (integer value u);

begin

blocked (u):= false;

for wB(u) do

begin

delete w from B(u);

if blocked(w) then UNBLOCK(w);

end end UNBLOCK

f :: false;

stack v;

blocked(v):- true;

L for wAK(v) do

if w-s then

begin

output circuit composed of stack followed by s;

f :- true;

end

else if--blocked(w) then

if CIRCUIT(w) then f true;

L2: if f then UNBLOCK(v)

else for wA:(v) do

if vqB(w) then put v on B(w);

unstack v;

CIRCUIT := f;

end CIRCUIT;

empty stack;

s:=l;
while s < n do

begin

A:= adjacency structure of strong component K with least vertex in subgraph of G induced by {s, s+ 1, n}; if A =! empty then

begin s := least vertex in V;

for I in V, do

begin blocked(i) :-- false;

B(i) = empty ,;

end;

L3: dummy :- CIRCUIT(s);

s:=s+l;

end

else s:= n;

end

end