Étant donné un graphique dirigé, affichez le cycle le plus long.

Règles

• Tout format d'entrée raisonnable est autorisé (par exemple, liste des bords, matrice de connectivité).
• Les étiquettes ne sont pas importantes, vous pouvez donc imposer des restrictions sur les étiquettes dont vous avez besoin et / ou que vous désirez, tant qu'elles ne contiennent pas d'informations supplémentaires non fournies dans l'entrée (par exemple, vous ne pouvez pas exiger que les nœuds dans les cycles soient étiquetés avec des entiers, et les autres nœuds sont étiquetés avec des chaînes alphabétiques).
• Un cycle est une séquence de nœuds qui sont tous connectés, et aucun nœud n'est répété, à l'exception du nœud qui est le début et la fin du cycle ( [1, 2, 3, 1]est un cycle, mais [1, 2, 3, 2, 1]ne l'est pas).
• Si le graphique est acyclique, le cycle le plus long a une longueur de 0 et devrait donc produire une sortie vide (par exemple une liste vide, pas de sortie du tout).
• La répétition du premier nœud à la fin de la liste des nœuds du cycle est facultative ( [1, 2, 3, 1]et [1, 2, 3]dénote le même cycle).
• S'il existe plusieurs cycles de la même longueur, l'un d'entre eux ou tous peuvent être sortis.
• Les prédéfinitions sont autorisées, mais si votre solution en utilise une, vous êtes encouragé à inclure une solution alternative qui n'utilise pas de prédéfinitions banalisantes (par exemple une prédéfinie qui génère tous les cycles). Cependant, la solution alternative ne comptera pas du tout dans votre score, elle est donc entièrement facultative.

Cas de test

Dans ces cas de test, l'entrée est donnée sous la forme d'une liste d'arêtes (où le premier élément est le nœud source et le deuxième élément est le nœud de destination), et la sortie est une liste de nœuds sans répétition du premier / dernier nœud.

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

22 octets sauvés grâce à JungHwan Min

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

est le caractère à usage privé de trois octets U+F3D5représentant \[DirectedEdge]. Fonction pure avec le premier argument #censé être une liste d'arêtes dirigées. Trouve des Allcycles de longueur au plus Infinitydans Graph@#, puis remplace la liste vide par la liste des auto-boucles. Les cycles sont représentés sous forme de listes d'arêtes et triés par longueur, nous prenons donc le dernier cycle de ce type, puis de toutes ses arêtes, nous prenons le premier argument afin d'obtenir une liste de sommets dans le format de sortie spécifié.

Si seulement Mathematica traitait les boucles comme un cycle de longueur 1( AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]donne True, sérieusement), alors nous pourrions économiser un autre 26octet:

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

Haskell , 157 154 150 octets

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

Essayez-le en ligne!

Merci @Laikoni et @Zgrab d'avoir enregistré un tas d'octets!

Il s'agit d'un programme très inefficace:

La première fonction #prend une liste de chemins l(une liste de listes de nombres) et essaie d'étendre les éléments de len ajoutant chaque bord possible (une liste de longueur 2) gà chaque élément de l. Cela ne se produit que si l'élément de ln'est pas déjà un cycle et si le nouveau nœud qui serait ajouté n'est pas déjà contenu dans l'élément de l. Si c'est déjà un cycle, on ne rajoute rien mais on l'ajoute à nouveau à la nouvelle liste de chemins, si on peut l'étendre, on ajoute le chemin étendu à la nouvelle liste, sinon on ne l'ajoute pas à la nouvelle liste .

Maintenant, la fonction hessaie à plusieurs reprises d'étendre ces chemins (en commençant par la liste des bords elle-même) jusqu'à ce que nous atteignions un point fixe, c'est-à-dire que nous ne pouvons plus étendre aucun chemin. À ce stade, nous n'avons que des cycles dans notre liste. Il suffit ensuite de choisir le cycle le plus long. Évidemment, les cycles apparaissent plusieurs fois dans cette liste car chaque rotation cyclique possible d'un cycle est à nouveau un cycle.

Pyth, 20 octets

eMefqhMT.>{eMT1s.pMy

Suite de tests

Prend une liste d'arêtes, comme dans les exemples.

Explication:

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 octets

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 fait tout le gros du travail, mais son format de sortie est plutôt unique et il ne détecte pas les cycles de longueur 1. Notez que cela ne fonctionne pas avec GNU tsort.

Vérification

--- 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 octets

5 octets enregistrés grâce à @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

Extrait de test

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 octets

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

Une solution de force brute: générer toutes les listes d'arêtes de longueurs croissantes jusqu'à la longueur de l'entrée, conserver celles qui sont des cycles, renvoyer la dernière. Prend le graphique au format [(1,2),(2,3),(2,4),(4,1)]. Essayez-le en ligne!

Explication

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 octets

Prend une matrice d'adjonction Aoù un bord (i,j)est désigné par un 1in A(i,j)et Aest nul dans toutes les autres entrées. La sortie est une liste d'un cycle le plus long. La liste est vide s'il n'y a pas de cycle du tout, et la liste inclut le début et la fin s'il y a un cycle. Il utilise1 indexation basée sur.

Cette solution n'utilise aucune fonction intégrée liée aux graphiques.

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

Malheureusement, cela ne fonctionne pas dans TryItOnline car il utilise une fonction dans une fonction, qui est récursive. Un peu de modification vous permet de l'essayer sur octave-online.net .

Pour le tout dernier test, j'ai trouvé un cycle plus long alternatif [0 2 1 4 3 5 7 8 9 11 10 6 0] (cette notation utilise une indexation basée sur 0)

Explication

L'approche de base ici est que nous effectuons un BFS à partir de chaque nœud et prenons soin de ne visiter aucun des nœuds intermédiaires à l'exception du nœud de départ. Avec cette idée, nous pouvons collecter tous les cycles possibles et choisir facilement le plus long.

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