Perché DFS non è abbastanza veloce nel controllare se un grafico è un albero - algoritmo, grafico, albero, pascal

Ho provato a risolvere questo problema Descrizione del problema Sembra che l'idea corretta sia quella di controllare se vengono forniti i graficiavere cicli (se è un albero). Tuttavia, il mio codice non è riuscito a superare il test 7, (Always Time Limit Exceeded), qualche idea su come renderlo più veloce? Ho usato DFS. Molte grazie Sì, finalmente è stato accettato. Il problema è dfs su ogni vertice, che non è necessario. la funzione dfs dovrebbe essere così.

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.

risposte:

2 per risposta № 1

Non so quasi nulla di Pascal, quindi potrei interpretare male quello che stai facendo, ma penso che il colpevole principale sia a fin dove deselezioni i vertici visitati. Questo ti costringe a fare un DFS da ogni vertice, mentre devi solo farne uno per componente.

Nel caso in cui sia presente più di un componente collegato, il movimento si interromperà

• perché un vertice punta a un vertice già segnato, nel qual caso ci fermiamo solo perché è stato trovato un ciclo
• perché il vertice non punta a nessuno (ma a se stesso), nel qual caso dobbiamo trovare il prossimo vertice non contrassegnato e avviare di nuovo un altro DFS da lì

Non devi preoccuparti della contabilità pertornare indietro poiché ogni vertice punta al massimo a un altro vertice in questo problema. Non è inoltre necessario preoccuparsi di quale DFS ha eseguito quale contrassegno, poiché ciascuno funzionerà comunque solo all'interno del componente collegato.

Nel caso in cui venga incontrato per primo un vertice che punta a se stesso, non dovrebbe essere ancora contrassegnato, ma saltato.

Soluzione alternativa utilizzando Set Union e Vertex / Edge Count

Poiché un albero ha la proprietà che il numero dibordi è uno in meno del numero di vertici, c'è un altro modo di pensare al problema: determinare (1) i componenti collegati e (2) confrontare il conteggio dei vertici e degli spigoli in ogni componente.

In molte lingue si dispone di una struttura di dati Set con metodi Union / Find a tempo quasi costante immediatamente disponibili. In questo caso la soluzione è facile e veloce: quasi lineare nel numero di spigoli.

Crea un insieme per ogni vertice che rappresenta il suocomponente collegato. Quindi elabora l'elenco dei bordi. Per ogni bordo, unisci gli insiemi rappresentati dai due vertici. Mentre procedi, tieni traccia del numero di vertici in ogni Set e dei bordi del numero. Stesso esempio:

Set iniziali

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

Bordo del processo da 1 a 2

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

Bordo del processo da 2 a 3

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

Bordo del processo da 3 a 4

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    3  0

Bordo del processo da 4 a 1

Vertex         1  2  3  4  5
Belongs to     S1 S1 S1 S1 S5

Set            S1 S5
Has # vertices 4  1
And # edges    4  0

E possiamo fermarci qui perché S1 a questo punto viola il conteggio dei vertici rispetto ai bordi degli alberi. C'è un ciclo S1. Non importa se il vertice 5 punta a se stesso oa qualcun altro.

Per i posteri, ecco un'implementazione in c. È passato un po 'di tempo, quindi perdona la sciatteria. Non è il più veloce, ma supera tutti i test entro il limite di tempo. La codifica del set disgiunto è direttamente da Pseudocodice di Wikipedia.

#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");
}
}

---