Traté de resolver este problema Descripción del problema Parece correcta la idea es comprobar si se dan gráficos.Tienen ciclos (ya sea un árbol). Sin embargo, mi código no pudo pasar la Prueba 7 (siempre que se superó el límite de tiempo) ¿Alguna idea de cómo hacer esto más rápido? Usé DFS. Muchas gracias Sí, finalmente fue aceptado. El problema es dfs en cada vértice, que es innecesario. La función dfs debería ser así.
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.
Respuestas
2 para la respuesta № 1No sé casi nada sobre Pascal, por lo que podría estar malinterpretando lo que está haciendo, pero creo que el culpable principal está en fin Donde desmarcarás los vértices visitados. Esto te obliga a hacer un DFS desde cada vértice, mientras que solo necesitas hacer uno por componente.
En el caso de que haya más de un componente conectado, el movimiento se detendrá
- porque un vértice apunta a un vértice ya marcado, en cuyo caso simplemente nos detenemos debido a que se ha encontrado un ciclo
- porque el vértice no apunta a nadie (sino a sí mismo), en cuyo caso necesitamos encontrar el siguiente vértice sin marcar y comenzar otro DFS desde allí
Usted no tiene que preocuparse por la contabilidad pararetroceder como cada vértice en la mayoría de los puntos a otro vértice en este problema. Tampoco hay que preocuparse por qué DFS hizo qué marcado, ya que cada uno solo funcionará dentro de su componente conectado de todos modos.
En el caso de que primero se encuentre un vértice que apunta a sí mismo, no debe estar marcado todavía, sino que debe saltarse.
Solución alternativa usando Set Union y Vertex / Edge Count
Dado que un árbol tiene la propiedad que el número debordes es uno menos que el número de vértices, hay otra manera de pensar en el problema: determine (1) los componentes conectados y (2) compare el recuento de vértices y bordes en cada componente.
En muchos idiomas, tiene una estructura de datos de conjuntos con métodos de unión / búsqueda de tiempo casi constante disponibles. En este caso, la solución es fácil y rápida: casi lineal en el número de bordes.
Crear un conjunto para cada vértice que representa sucomponente conectado Luego procesa tu lista de bordes. Para cada borde, une los conjuntos representados por los dos vértices. A medida que avanza, realice un seguimiento del número de vértices en cada Conjunto y los bordes de los números. Mismo ejemplo:
Conjuntos iniciales
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
Procesar borde de 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
Procesar el borde de 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
Procesar el borde de 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
Procesar borde de 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
Y podemos detenernos aquí porque S1 En este punto, se viola el vértice contra el recuento de aristas de los árboles. Hay un ciclo en S1. No importa si el vértice 5 apunta a sí mismo oa otra persona.
Para la posteridad, aquí hay una implementación en do. Ha pasado un tiempo, así que perdona el descuido. No es el más rápido, pero pasa todas las pruebas dentro del límite de tiempo. La codificación del conjunto disjunto es directamente de Pseudocódigo de 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");
}
}