Ich habe versucht, dieses Problem zu lösen Problembeschreibung Es scheint die richtige Idee zu sein, zu überprüfen, ob die Diagramme angegeben sindZyklen haben (ob ein Baum ist). Mein Code konnte jedoch Test 7 (Always Time Limit Exceeded) nicht bestehen. Ich habe DFS verwendet. Vielen Dank Ja, wurde endlich akzeptiert. Das Problem ist dfs für jeden Vertex, was nicht notwendig ist. Die DFS-Funktion sollte so aussehen.
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.
Antworten:
2 für die Antwort № 1Ich weiß so gut wie nichts über Pascal, also könnte ich falsch interpretieren, was Sie tun, aber ich denke, der Haupttäter ist bei fin Hier heben Sie die Markierung für besuchte Scheitelpunkte auf. Dies zwingt Sie dazu, eine DFS von jedem Scheitelpunkt aus durchzuführen, während Sie nur eine pro Komponente ausführen müssen.
Wenn mehr als eine Komponente angeschlossen ist, wird die Bewegung angehalten
- weil ein Scheitelpunkt auf einen bereits markierten Scheitelpunkt zeigt. In diesem Fall halten wir nur an, weil ein Zyklus gefunden wurde
- weil der Scheitelpunkt auf niemanden zeigt (außer auf sich selbst). In diesem Fall müssen wir den nächsten nicht markierten Scheitelpunkt finden und von dort aus einen neuen DFS starten
Sie brauchen sich keine Sorgen um die Buchhaltung zu machenDas Zurückverfolgen jedes Scheitelpunkts zeigt in diesem Problem höchstens auf einen anderen Scheitelpunkt. Sie müssen sich auch keine Gedanken darüber machen, welche DFS welche Markierung vorgenommen hat, da jede nur innerhalb der verbundenen Komponente funktioniert.
Wenn ein Scheitelpunkt, der auf sich selbst zeigt, zuerst angetroffen wird, sollte er noch nicht markiert sein, sondern übersprungen werden.
Alternative Lösung mit Set Union und Vertex / Edge Count
Da ein Baum die Eigenschaft hat, dass die Anzahl derKanten sind um eins kleiner als die Anzahl der Scheitelpunkte. Es gibt eine andere Möglichkeit, das Problem zu betrachten: Ermitteln Sie (1) die verbundenen Komponenten und (2) vergleichen Sie die Anzahl der Kanten und Scheitelpunkte in jeder Komponente.
In vielen Sprachen steht Ihnen eine Set-Datenstruktur mit zeitlich nahezu konstanten Union / Find-Methoden zur Verfügung. In diesem Fall ist die Lösung einfach und schnell - nahezu linear in der Anzahl der Kanten.
Erstellen Sie ein Set für jeden Scheitelpunkt, der seinen repräsentiertangeschlossene Komponente. Dann bearbeiten Sie Ihre Kantenliste. Vereinigen Sie für jede Kante die Mengen, die durch die beiden Scheitelpunkte dargestellt werden. Behalten Sie dabei die Anzahl der Scheitelpunkte in jedem Set und die Anzahl der Kanten im Auge. Gleiches Beispiel:
Anfangssätze
Vertex 1 2 3 4 5
Belongs to S1 S2 S3 S4 S5
Set S1 S2 S3 S4 S5
Has # vertices 1 1 1 1 1
And # edges 0 0 0 0 0
Kante von 1 nach 2 bearbeiten
Vertex 1 2 3 4 5
Belongs to S1 S1 S3 S4 S5
Set S1 S3 S4 S5
Has # vertices 2 1 1 1
And # edges 1 0 0 0
Kante von 2 nach 3 bearbeiten
Vertex 1 2 3 4 5
Belongs to S1 S1 S1 S4 S5
Set S1 S4 S5
Has # vertices 3 1 1
And # edges 2 0 0
Kante von 3 bis 4 bearbeiten
Vertex 1 2 3 4 5
Belongs to S1 S1 S1 S1 S5
Set S1 S5
Has # vertices 4 1
And # edges 3 0
Kante von 4 auf 1 bearbeiten
Vertex 1 2 3 4 5
Belongs to S1 S1 S1 S1 S5
Set S1 S5
Has # vertices 4 1
And # edges 4 0
Und wir können hier aufhören, weil S1 An dieser Stelle wird die Anzahl der Ecken und Kanten von Bäumen verletzt. Es ist ein Zyklus in S1. Es spielt keine Rolle, ob Vertex 5 auf sich selbst oder auf eine andere Person zeigt.
Für die Nachwelt ist hier eine Implementierung in c. Es ist eine Weile her, also vergib die Schlamperei. Es ist nicht die schnellste, aber es besteht alle Tests innerhalb des Zeitlimits Wikipedia "s Pseudocode.
#include <stdio.h>
struct ds_node
{
struct ds_node *parent;
int rank;
};
struct ds_node v[25001];
void ds_makeSet(struct ds_node *x)
{
x->parent = x;
x->rank = 0;
}
struct ds_node* ds_find(struct ds_node *x)
{
if (x->parent != x) x->parent = ds_find(x->parent);
return x->parent;
}
int ds_union(struct ds_node *x, struct ds_node *y)
{
struct ds_node * xRoot;
struct ds_node * yRoot;
xRoot = ds_find(x);
yRoot = ds_find(y);
if (xRoot == yRoot) return 0;
if (xRoot->rank < yRoot->rank)
{
xRoot->parent = yRoot;
}
else if (xRoot->rank > yRoot->rank)
{
yRoot->parent = xRoot;
}
else
{
yRoot->parent = xRoot;
xRoot->rank++;
}
return 1;
}
int test(int n)
{
int i, e, z = 0;
for(i=1;i<=n;i++)
{
ds_makeSet(&v[i]);
}
for(i=1;i<=n;i++)
{
scanf("%d",&e);
if (e)
{
if ( !ds_union(&v[i],&v[e]) )
{
for(i++;i<=n;i++) scanf("%d",&e);
return 0;
}
}
else
{
z++;
}
}
return (z == 1);
}
int main()
{
int runs; int n;
scanf("%d", &runs);
while(runs--)
{
scanf("%d", &n);
getc(stdin);
test(n) ? puts("YES") : puts("NO");
}
}