Biorąc pod uwagę ukierunkowany wykres, generuj najdłuższy cykl.

Zasady

• Dozwolony jest dowolny rozsądny format wejściowy (np. Lista krawędzi, macierz połączeń).
• Etykiety nie są ważne, więc możesz nałożyć ograniczenia na etykiety, których potrzebujesz i / lub pragniesz, o ile nie zawierają one dodatkowych informacji, które nie zostały podane w danych wejściowych (np. Nie możesz wymagać, aby węzły w cyklach były oznaczone liczbami całkowitymi, a inne węzły są oznaczone łańcuchami alfabetycznymi).
• Cykl jest sekwencją połączonych węzłów i żaden węzeł nie jest powtarzany poza węzłem, który jest początkiem i końcem cyklu ( [1, 2, 3, 1]jest cyklem, ale [1, 2, 3, 2, 1]nie jest).
• Jeśli wykres jest acykliczny, najdłuższy cykl ma długość 0, a zatem powinien dać pusty wynik (np. Pusta lista, brak danych wyjściowych).
• Powtórzenie pierwszego węzła na końcu listy węzłów w cyklu jest opcjonalne ( [1, 2, 3, 1]i[1, 2, 3] oznacza ten sam cykl).
• Jeśli istnieje wiele cykli o tej samej długości, można wygenerować jeden lub wszystkie z nich.
• Wbudowane są dozwolone, ale jeśli twoje rozwiązanie korzysta z jednego, zachęcamy do dołączenia alternatywnego rozwiązania, które nie wykorzystuje trywialnych wbudowanych (np. Wbudowanego, który generuje wszystkie cykle). Jednak alternatywne rozwiązanie w ogóle nie będzie wliczane do wyniku, więc jest całkowicie opcjonalne.

Przypadki testowe

W tych przypadkach testowych dane wejściowe są podawane jako lista krawędzi (gdzie pierwszy element jest węzłem źródłowym, a drugi element jest węzłem docelowym), a dane wyjściowe to lista węzłów bez powtarzania pierwszego / ostatniego węzła.

[(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 bajtów

Zaoszczędzono aż 22 bajty dzięki JungHwan Min

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

to trzy bajtowy prywatny znak U+F3D5reprezentujący \[DirectedEdge]. Czysta funkcja z pierwszym argumentem #powinna być listą ukierunkowanych krawędzi. Znajduje Allcykle długości co najwyżej InfinitywGraph@# , a następnie zastępuje pustą listę z listą samorządów pętli. Cykle są reprezentowane jako listy krawędzi i posortowane według długości, więc bierzemy ostatni taki cykl, a następnie ze wszystkich jego krawędzi bierzemy pierwszy argument, aby uzyskać listę wierzchołków w określonym formacie wyjściowym.

Gdyby tylko Mathematica traktował pętle jako cykl długości 1( AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]daje Truepoważnie), moglibyśmy zapisać kolejne 26bajty:

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

Haskell , 157 154 150 bajtów

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

Wypróbuj online!

Dzięki @Laikoni i @Zgrab za uratowanie wielu bajtów!

To bardzo nieefektywny program:

Pierwsza funkcja #pobiera listę ścieżek l(listę list liczb) i próbuje rozszerzyć elementy l, przygotowując każdą możliwą krawędź (listę długości 2) gdla każdego elementu l. Dzieje się tak tylko wtedy, gdy element lnie jest już cyklem i jeśli nowy węzeł, który byłby poprzedzony, nie jest już zawarty w elemenciel . Jeśli jest to już cykl, nie przygotowujemy niczego, ale dodajemy go ponownie do nowej listy ścieżek, jeśli możemy go rozszerzyć, dodajemy rozszerzoną ścieżkę do nowej listy, w przeciwnym razie nie dodamy jej do nowej listy .

Teraz funkcja hwielokrotnie próbuje wydłużyć te ścieżki (zaczynając od samej listy krawędzi), aż dojdziemy do ustalonego punktu, tzn. Nie możemy już przedłużyć żadnej ścieżki. W tym momencie mamy tylko cykle na naszej liście. Zatem wystarczy wybrać najdłuższy cykl. Oczywiście cykle pojawiają się na tej liście wiele razy, ponieważ każdy możliwy cykliczny obrót cyklu jest znowu cyklem.

Pyth, 20 bajtów

eMefqhMT.>{eMT1s.pMy

Zestaw testowy

Pobiera listę krawędzi, jak w przykładach.

Wyjaśnienie:

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 bajtów

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 wykonuje wszystkie ciężkie operacje podnoszenia, ale jego format wyjściowy jest raczej unikalny i nie wykrywa cykli długości 1. Zauważ, że nie działa to z GNU tsort.

Weryfikacja

--- 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 139 bajtów

Zaoszczędź 5 bajtów dzięki @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

Testowy fragment kodu

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 bajtów

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])]

Rozwiązanie brutalnej siły: wygeneruj wszystkie listy krawędzi o coraz większej długości aż do długości wejścia, zachowaj te, które są cyklami, zwróć ostatnią. Przyjmuje wykres w formacie [(1,2),(2,3),(2,4),(4,1)]. Wypróbuj online!

Wyjaśnienie

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 bajtów

Pobiera macierz adjecencji, w Aktórej krawędź (i,j)jest oznaczona przez 1in A(i,j), iA wynosi zero we wszystkich innych pozycjach. Wynik jest listą najdłuższego cyklu. Lista jest pusta, jeśli w ogóle nie ma cyklu, a lista zawiera początek i punkt końcowy, jeśli istnieje cykl. Korzysta z 1indeksowania na podstawie.

To rozwiązanie nie korzysta z żadnych wbudowanych funkcji związanych z wykresami.

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

Niestety nie działa to w TryItOnline, ponieważ używa funkcji wewnątrz funkcji, która jest rekurencyjna. Odrobina modyfikacji pozwala wypróbować ją na octave-online.net .

W ostatnim przypadku testowym znalazłem alternatywny najdłuższy cykl [0 2 1 4 3 5 7 8 9 11 10 6 0](ta notacja wykorzystuje indeksowanie oparte na 0)

Wyjaśnienie

Podstawowe podejście polega na tym, że wykonujemy BFS z każdego węzła i uważamy, aby nie odwiedzać ponownie żadnego z węzłów pośrednich, z wyjątkiem węzła początkowego. Dzięki temu pomysłowi możemy zebrać wszystkie możliwe cykle i łatwo wybrać najdłuższy.

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