Опитах се да реша този проблем Описание на проблема Изглежда правилната идея е да проверите дали дадените графики имат цикли (дали е дърво). Моят код обаче не можа да премине тест 7 (винаги превишено времево ограничение), някаква идея как да направя това по-бързо? Използвах DFS. Много благодаря Да, най-накрая ме приеха. Проблемът е dfs на всеки връх, което е ненужно. функцията dfs трябва да е така.
function dfs(idx: integer; id: integer): boolean;
begin
if (visited[idx] = id) then
begin
Result := false;
Exit;
end;
if (tree[idx] <> 0) then
begin
visited[idx] := id;
Result := dfs(tree[idx], id);
Exit;
end;
Result := true;
end;
program Project2;
{$APPTYPE CONSOLE}
var
i, m, j, n, k: integer;
tree: array [1 .. 25001] of integer;
visited: array [1 .. 25001] of boolean;
function dfs(idx: integer): boolean;
label
fin;
var
buf: array[1 .. 25001] of integer;
i, cnt: integer;
begin
cnt := 1;
while (true) do
begin
if (visited[idx]) then
begin
Result := false;
goto fin;
end;
if (tree[idx] <> 0) then
begin
visited[idx] := true;
buf[cnt] := idx;
Inc(cnt);
idx := tree[idx];
end
else
begin
break;
end;
end;
Result := true;
fin:
for i := 1 to cnt - 1 do
begin
visited[buf[i]] := false;
end;
end;
function chk(n: integer): boolean;
var
i: integer;
begin
for i := 1 to n do
begin
if (tree[i] = 0) then continue;
if (visited[i]) then continue;
if (dfs(i) = false) then
begin
Result := false;
Exit;
end;
end;
Result := true;
end;
begin
Readln(m);
for i := 1 to m do
begin
Readln(n);
k := 0;
for j := 1 to n do
begin
Read(tree[j]);
if (tree[j] = 0) then
begin
Inc(k);
end;
end;
if (k <> 1) then
begin
Writeln('NO');
end
else
if (chk(n)) then
begin
Writeln('YES');
end
else
begin
Writeln('NO');
end;
Readln;
end;
//Readln;
end.
fin:. Това ви принуждава да правитеDFSот всеки връх, което е ненужно тук. - person A. Webb schedule 06.11.2012