Dado um gráfico direcionado, produza o ciclo mais longo.

Regras

• Qualquer formato de entrada razoável é permitido (por exemplo, lista de bordas, matriz de conectividade).
• Os rótulos não são importantes, portanto, você pode impor restrições aos rótulos de que precisa e / ou deseja, desde que não contenham informações adicionais não fornecidas na entrada (por exemplo, você não pode exigir que os nós nos ciclos sejam rotulados com números inteiros e outros nós são rotulados com seqüências alfabéticas).
• Um ciclo é uma sequência de nós que estão todos conectados e nenhum nó é repetido, exceto o nó que é o início e o fim do ciclo ( [1, 2, 3, 1]é um ciclo, mas [1, 2, 3, 2, 1]não é).
• Se o gráfico for acíclico, o ciclo mais longo terá o comprimento 0 e, portanto, deverá produzir uma saída vazia (por exemplo, lista vazia, nenhuma saída).
• Repetir o primeiro nó no final da lista de nós no ciclo é opcional ( [1, 2, 3, 1]e [1, 2, 3]denota o mesmo ciclo).
• Se houver vários ciclos do mesmo comprimento, qualquer um ou todos eles poderão ser produzidos.
• Builtins são permitidos, mas se a sua solução usa um, recomendamos que você inclua uma solução alternativa que não use trivializing builtins (por exemplo, um builtin que produz todos os ciclos). No entanto, a solução alternativa não conta para a sua pontuação, portanto é totalmente opcional.

Casos de teste

Nesses casos de teste, a entrada é fornecida como uma lista de arestas (onde o primeiro elemento é o nó de origem e o segundo elemento é o nó de destino) e a saída é uma lista de nós sem repetição do primeiro / último nó.

[(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

Economizou 22 bytes graças a JungHwan Min

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

é o caractere de uso privado de três bytes que U+F3D5representa \[DirectedEdge]. Função pura com o primeiro argumento #esperado como uma lista de arestas direcionadas. Localiza Allciclos de duração no máximo , Infinityem Graph@#seguida, substitui a lista vazia pela lista de auto-loops. Os ciclos são representados como listas de arestas e classificados por comprimento; portanto, pegamos o último ciclo desse tipo; depois, de todas as arestas, pegamos o primeiro argumento para obter uma lista de vértices no formato de saída especificado.

Se apenas o Mathematica tratasse loops como um ciclo de duração 1( AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]dá True, sério), poderíamos salvar outros 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

Experimente online!

Obrigado @Laikoni e @Zgrab por salvar um monte de bytes!

Este é um programa muito ineficiente:

A primeira função #pega uma lista de caminhos l(uma lista de listas de números) e tenta estender os elementos lanexando todas as arestas possíveis (uma lista de comprimento 2) ga cada elemento de l. Isso acontece apenas se o elemento de ljá não for um ciclo e se o novo nó que seria acrescentado ainda não estiver contido no elemento de l. Se já é um ciclo, não acrescentamos nada antes, mas o adicionamos novamente à nova lista de caminhos. Se pudermos estendê-lo, adicionamos o caminho estendido à nova lista, caso contrário, não o adicionamos à nova lista. .

Agora, a função htenta repetidamente estender esses caminhos (começando pela própria lista de arestas) até chegarmos a um ponto fixo, ou seja, não podemos mais estender nenhum caminho. Neste ponto, temos apenas ciclos em nossa lista. Então é apenas uma questão de escolher o ciclo mais longo. Obviamente, os ciclos aparecem várias vezes nesta lista, pois toda rotação cíclica possível de um ciclo é novamente um ciclo.

Pitão, 20 bytes

eMefqhMT.>{eMT1s.pMy

Suíte de teste

Leva uma lista de arestas, como nos exemplos.

Explicação:

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

O tsort faz todo o trabalho pesado, mas seu formato de saída é bastante único e não detecta ciclos de comprimento 1. Observe que isso não funciona com o GNU tsort.

Verificação

--- 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 156 145 139 bytes

Guardado 5 bytes graças 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

Snippet de teste

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 , 109 108 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])]

Uma solução de força bruta: gere todas as listas de arestas de comprimentos crescentes até o comprimento da entrada, mantenha as que são ciclos, retorne a última. Pega o gráfico no formato [(1,2),(2,3),(2,4),(4,1)]. Experimente online!

Explicação

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 uma matriz de adjecência Aonde uma aresta (i,j)é denotada por um 1in A(i,j)e Aé zero em todas as outras entradas. A saída é uma lista do ciclo mais longo. A lista está vazia, se não houver ciclo, e a lista inclui o ponto inicial e final, se houver um ciclo. Ele usa 1indexação baseada em.

Esta solução não usa funções internas relacionadas a 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

Infelizmente, isso não é executado no TryItOnline, pois usa uma função dentro de uma função, que é recursiva. Um pouco de modificação permite que você experimente no octave-online.net .

No último caso de teste, encontrei um ciclo mais longo alternativo [0 2 1 4 3 5 7 8 9 11 10 6 0](essa notação usa indexação baseada em 0)

Explicação

A abordagem básica aqui é que executamos um BFS de todos os nós e cuidamos para não visitar nenhum dos nós intermediários novamente, exceto o nó inicial. Com essa idéia, podemos coletar todos os ciclos possíveis e escolher facilmente o mais longo.

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