Dado un gráfico dirigido, genera el ciclo más largo.

Reglas

• Se permite cualquier formato de entrada razonable (por ejemplo, lista de bordes, matriz de conectividad).
• Las etiquetas no son importantes, por lo que puede imponer restricciones a las etiquetas que necesita y / o desea, siempre que no contengan información adicional no proporcionada en la entrada (por ejemplo, no puede exigir que los nodos en los ciclos sean etiquetados con enteros y otros nodos están etiquetados con cadenas alfabéticas).
• Un ciclo es una secuencia de nodos que están todos conectados, y ningún nodo se repite, excepto el nodo que es el inicio y el final del ciclo ( [1, 2, 3, 1]es un ciclo, pero [1, 2, 3, 2, 1]no lo es).
• Si el gráfico es acíclico, el ciclo más largo tiene una longitud 0 y, por lo tanto, debería producir una salida vacía (por ejemplo, lista vacía, sin salida).
• La repetición del primer nodo al final de la lista de nodos en el ciclo es opcional ( [1, 2, 3, 1]y [1, 2, 3]denota el mismo ciclo).
• Si hay múltiples ciclos de la misma longitud, se puede generar uno o todos ellos.
• Las incorporaciones están permitidas, pero si su solución usa una, se le recomienda que incluya una solución alternativa que no utilice incorporaciones trivializantes (por ejemplo, una creación que genera todos los ciclos). Sin embargo, la solución alternativa no contará para su puntaje, por lo que es completamente opcional.

Casos de prueba

En estos casos de prueba, la entrada se proporciona como una lista de aristas (donde el primer elemento es el nodo de origen y el segundo elemento es el nodo de destino), y la salida es una lista de nodos sin repetición del primer / último nodo.

[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]

Mathematica, 80 58 bytes

Ahorró la friolera de 22 bytes gracias a JungHwan Min

(FindCycle[#,∞,All]/.{}->{Cases[#,v_v_]})[[-1,;;,1]]&

es el carácter de uso privado de tres bytes que U+F3D5representa \[DirectedEdge]. La función pura con el primer argumento se #espera que sea una lista de aristas dirigidas. Encuentra Allciclos de duración como máximo Infinityen Graph@#, luego reemplaza la lista vacía con la lista de bucles automáticos. Los ciclos se representan como listas de aristas y se ordenan por longitud, por lo que tomamos el último ciclo, luego de todas sus aristas tomamos el primer argumento para obtener una lista de vértices en el formato de salida especificado.

Si solo Mathematica tratara los bucles como un ciclo de longitud 1( AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]da True, en serio), entonces podríamos guardar otros 26bytes:

FindCycle[#,∞,All][[-1,;;,1]]&

Haskell , 157 154 150 bytes

import Data.List
g#l=nub[last$(e:d):[d|p==last q||e`elem`init d]|d@(p:q)<-l,[e,f]<-g,p==f]
h g=snd$maximum$((,)=<<length)<$>[]:until((==)=<<(g#))(g#)g

Pruébalo en línea!

¡Gracias @Laikoni y @Zgrab por guardar un montón de bytes!

Este es un programa muy ineficiente:

La primera función #toma una lista de rutas l(una lista de listas de números) e intenta extender los elementos lal anteponer cada borde posible (una lista de longitud 2) ga cada elemento de l. Esto sucede solo si el elemento de lno es ya un ciclo y si el nuevo nodo que se antepondrá no está contenido en el elemento de l. Si ya es un ciclo, no anteponemos nada, sino que lo agregamos nuevamente a la nueva lista de rutas, si podemos extenderlo, agregamos la ruta extendida a la nueva lista, de lo contrario no la agregamos a la nueva lista .

Ahora, la función hintenta repetidamente extender esas rutas (comenzando con la lista de bordes en sí) hasta llegar a un punto fijo, es decir, no podemos extender ninguna ruta más. En este punto solo tenemos ciclos en nuestra lista. Entonces es solo cuestión de elegir el ciclo más largo. Obviamente, los ciclos aparecen varias veces en esta lista, ya que cada posible rotación cíclica de un ciclo es nuevamente un ciclo.

Pyth, 20 bytes

eMefqhMT.>{eMT1s.pMy

Banco de pruebas

Toma una lista de bordes, como en los ejemplos.

Explicación:

eMefqhMT.>{eMT1s.pMy
eMefqhMT.>{eMT1s.pMyQ    Variable introduction
                   yQ    Take all subsets of the input, ordered by length
                .pM      Reorder the subsets in all possible ways
               s         Flatten
                         (This should be a built in, I'm going to make it one.)
   f                     Filter on (This tests that we've found a cycle)
    qhMT                 The list of first elements of edges equals
           eMT           The last elements
         .>   1          Rotated right by 1
        {                Deduplicated (ensures no repeats, which would not be a
                         simple cycle)
  e                      Take the last element, which will be the longest one.
eM                       Take the last element of each edge, output.

Bash + bsdutils, 129 bytes

sed 's/^\(.*\) \1$/x \1 \1 x/'|sort|(tsort -l>&-)|&tr c\\n '
 '|sed 's/x //g'|awk 'm<NF{m=NF;gsub(/[^0-9 ] ?/,"");print}'|tail -1

tsort hace todo el trabajo pesado, pero su formato de salida es bastante único y no detecta ciclos de longitud 1. Tenga en cuenta que esto no funciona con GNU tsort.

Verificación

--- t1 ---
0
--- t2 ---
--- t3 ---
0 1
--- t4 ---
1 2 4 5
--- t5 ---
0 2 4 6 8
--- t6 ---
0 2 1 6 3 7 4 8 9 5
--- t7 ---
0 11 10 3 1 2 4 7 5 8 9 6

JavaScript (ES6), 173 163 156 145 139 bytes

Guardado 5 bytes gracias a @Neil

f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

Fragmento de prueba

f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

g=a=>console.log("Input:",JSON.stringify(a),"Output:",JSON.stringify(f(a)))

g([[0,0]])
g([[0,1],[1,2]])
g([[0,1],[1,0]])
g([[0,1],[1,2],[2,0]])
g([[0,1],[1,2],[1,3],[2,4],[4,5],[5,1]])
g([[0,1],[0,2],[1,3],[2,4],[3,0],[4,6],[6,8],[8,0]])

Haskell , 109108 bytes

import Data.List
f g=last$[]:[b|n<-[1..length g],e:c<-mapM(\_->g)[1..n],b<-[snd<$>e:c],b==nub(fst<$>c++[e])]

Una solución de fuerza bruta: genere todas las listas de bordes de longitudes crecientes hasta la longitud de la entrada, mantenga los que son ciclos, devuelva el último. Toma el gráfico en el formato [(1,2),(2,3),(2,4),(4,1)]. Pruébalo en línea!

Explicación

f g=                    -- Define function f on input g as
  last$                 -- the last element of the following list
  []:                   -- (or [], if the list is empty):
  [b|                   --  lists of vertices b where
   n<-[1..length g],    --  n is between 1 and length of input,
   e:c<-                --  list of edges with head e and tail c is drawn from
    mapM(\_->g)[1..n],  --  all possible ways of choosing n edges from g,
   b<-[snd<$>e:c],      --  b is the list of second elements in e:c,
   b==                  --  and b equals
    nub(fst<$>c++[e])]  --  the de-duplicated list of first elements
                        --  in the cyclic shift of e:c.

MATLAB, 291 260 bytes

Toma una matriz adjecency Adonde un borde (i,j)se denota por una 1en A(i,j), y Aes cero en todas las otras entradas. La salida es una lista de un ciclo más largo. La lista está vacía si no hay ningún ciclo, y la lista incluye el inicio y el punto final si hay un ciclo. Utiliza 1indexación basada en.

Esta solución no utiliza ninguna función integrada relacionada con gráficos.

function c=f(A);N=size(A,1);E=eye(N);c=[];for j=1:N;l=g(j);if numel(l)>numel(c);c=l;end;end;function p=g(p)if ~any(find(p(2:end)==p(1)))e=E(p(end),:)Q=find(e*A)k=[];for q=Q;if ~ismember(q,p(2:end))n=g([p,q]);if numel(n)>numel(k);k=n;end;end;end;p=k;end;end;end

Lamentablemente, esto no se ejecuta en TryItOnline, ya que utiliza una función dentro de una función, que es recursiva. Un poco de modificación le permite probarlo en octave-online.net .

Para el último caso de prueba, encontré un ciclo más largo alternativo [0 2 1 4 3 5 7 8 9 11 10 6 0](esta notación usa indexación basada en 0)

Explicación

El enfoque básico aquí es que realizamos un BFS desde cada nodo y nos aseguramos de no visitar ninguno de los nodos intermedios, excepto el nodo de inicio. Con esa idea, podemos recopilar todos los ciclos posibles y elegir fácilmente el más largo.

function c=f(A);
N=size(A,1);
E=eye(N);
c=[]; % current longest cycle
for j=1:N;                                      % iterate over all nodes
    l=getLongestCycle(j);                       % search the longest cycle through the current node
    if numel(l)>numel(c);                       % if we find a longer cycle, update our current longest cycle
        c=l;
    end;

end;

    function p=getLongestCycle(p);              % get longest cycle from p(1) using recursion
        if ~any(find(p(2:end)==p(1)));          % if we just found a cycle, return the cycle do nothing else, OTHERWISE:
            e=E(p(end),:);                      % from the last node, compute all outgoing edges
            Q=find(e*A);                        
            k=[];                               
            for q=Q;                            % iterate over all outogoin edges
                if ~ismember(q,p(2:end));       % if we haven't already visited this edge,
                    n=getLongestCycle([p,q]);   % recursively search from the end node of this edge
                    if numel(n)>numel(k);       % if this results in a longer cycle, update our current longest cycle
                        k=n;
                    end;
                end;
            end;
            p=k;
        end;
    end; 
end