O desafio

Seu programa deve receber 3 entradas:

• Um número inteiro positivo que é o número de variáveis,
• Um conjunto de pares não ordenados de números inteiros não negativos, em que cada par representa uma igualdade entre variáveis ​​e
• Um número inteiro positivo que representa a variável inicial,

Ele deve retornar um conjunto de números inteiros não negativos que representam todas as variáveis ​​que podem ser mostradas transitivamente iguais à variável inicial (incluindo a própria variável inicial).

Em outras palavras, dadas as entradas N, Ee S, retornar um conjunto Q, de tal forma que:

• S ∈ Q.
• Se Z ∈ Qe (Y = Z) ∈ E, então Y ∈ Q.
• Se Z ∈ Qe (Z = Y) ∈ E, então Y ∈ Q.

Isso também pode ser expresso como um problema da teoria dos grafos :

Dado um gráfico não direcionado e um vértice no gráfico, liste os vértices em seu componente conectado .

Especificações

• Você pode optar por usar a indexação com base em 0 ou em 1.
• A primeira entrada conta o número de variáveis ​​presentes, onde as variáveis ​​são fornecidas como números. Como alternativa, você não pode receber essa entrada; nesse caso, assume-se que seja igual ao índice de variável mais alto presente ou a um mais que isso, dependendo do seu esquema de indexação.
• Você pode assumir que a entrada está bem formada: você não receberá variáveis ​​fora do intervalo especificado pela primeira entrada. Por exemplo, 3, [1 = 2, 2 = 0], 1é uma entrada válida, enquanto 4, [1 = 719, 1 = 2, 3 = 2], -3não é.
• Você não pode assumir que qualquer variável terá igualdades associadas a ela. Se for fornecida uma terceira entrada "solitária" (sem igual), a saída correta é um conjunto de singleton contendo apenas essa entrada (já que é igual a si próprio).
• Você pode assumir que as igualdades não conterão uma igualdade de uma variável para si mesma e que a mesma igualdade não será dada várias vezes (isso inclui coisas como 1 = 2e 2 = 1).
• Você pode supor que todos os números inteiros fornecidos estejam dentro do intervalo representável do seu idioma.
• Você pode pegar a segunda entrada em qualquer formato razoável.

Aqui estão alguns formatos razoáveis:

0 = 2
0 = 3
1 = 0

{(0, 2), (0, 3), (1, 0)}

[0, 2, 0, 3, 1, 0]

0 2 0 3 1 0

Graph[{{0, 2}, {0, 3}, {1, 0}}]

[0 = 2, 0 = 3, 1 = 0]

• Você pode imprimir em qualquer formato razoável (por exemplo, conjunto, lista etc.). A ordem é irrelevante.

Pontuação

Isso é código-golfe , então o programa válido mais curto (em bytes) vence.

Casos de teste (indexados 0)

3, [1 = 2, 2 = 0], 1                      -> {0, 1, 2}
5, [0 = 2, 0 = 3, 1 = 2], 3               -> {0, 1, 2, 3}
6, [0 = 3, 1 = 3, 2 = 4, 5 = 1], 4        -> {2, 4}
6, [0 = 3, 1 = 3, 2 = 4, 5 = 1], 5        -> {0, 1, 3, 5}
5, [0 = 1, 2 = 0, 0 = 3, 4 = 0], 2        -> {0, 1, 2, 3, 4}
6, [0 = 1, 1 = 2, 2 = 3, 3 = 4, 4 = 5], 3 -> {0, 1, 2, 3, 4, 5}
4, [0 = 1, 1 = 2, 2 = 0], 3               -> {3}
5, [0 = 2, 2 = 4], 2                      -> {0, 2, 4}
8, [], 7                                  -> {7}

Casos de teste (1 indexados)

3, [2 = 3, 3 = 1], 2                      -> {1, 2, 3}
5, [1 = 3, 1 = 4, 2 = 3], 4               -> {1, 2, 3, 4}
6, [1 = 4, 2 = 4, 3 = 5, 6 = 2], 5        -> {3, 5}
6, [1 = 4, 2 = 4, 3 = 5, 6 = 2], 6        -> {1, 2, 4, 6}
5, [1 = 2, 3 = 1, 1 = 4, 5 = 1], 3        -> {1, 2, 3, 4, 5}
6, [1 = 2, 2 = 3, 3 = 4, 4 = 5, 5 = 6], 4 -> {1, 2, 3, 4, 5, 6}
4, [1 = 2, 2 = 3, 3 = 1], 4               -> {4}
5, [1 = 3, 3 = 5], 3                      -> {1, 3, 5}
8, [], 8                                  -> {8}

Braquilog , 22 bytes

{tc⊇,?k.&¬(t∋;.xȮ)∧}ᶠt

Experimente online!

Explicação

{tc⊇,?k.&¬(t∋;.xȮ)∧}ᶠt  Input is a pair, say [2,[[1,3],[2,4],[5,2]]]
{                   }ᶠ   Find all outputs of this predicate:
 t                        Tail: [[1,3],[2,4],[5,2]]
  c                       Concatenate: [1,3,2,4,5,2]
   ⊇                      Choose a subset: [4,5]
    ,?                    Append the input: [4,5,2,[[1,3],[2,4],[5,2]]]
      k                   Remove the last element: [4,5,2]
       .                  This list is the output.
        &¬(      )∧       Also, the following is not true:
           t∋              There is a pair P in the second part of the input.
             ;.x           If you remove from P those elements that occur in the output,
                Ȯ          the result is a one-element list.
                      t  Take the last one of these outputs, which is the shortest one.

Python 2 , 65 63 bytes

^{-2 bytes graças a ovs}

def f(e,s):b={s};exec"for p in e:b|=b&p and p\n"*len(e);print b

Experimente online!

Pitão , 12 bytes

u|sf@TGQG.{E

Suíte de teste.

Limpo , 85 81 bytes

import StdEnv
$l=limit o iterate(\v=removeDup(flatten[v:filter(isAnyMember v)l]))

Experimente online!

Define a função $ :: [[Int]] -> ([Int] -> [Int])

Wolfram Language (Mathematica) , 32 bytes

#~VertexComponent~#2~Check~{#2}&

Formato de entrada: {2<->3, 3<->1}, 3 . Não recebe a primeira entrada.

Experimente online!

Linguagem de script da operação Flashpoint , 364 bytes

f={t=_this;r=t select 1;i=0;while{i<t select 0}do{call format["V%1=[%1]",i];i=i+1};i=0;while{i<count r}do{call format(["V%1=V%1+V%2;V%2=V%1"]+(r select i));i=i+1};l=call format["V%1",t select 2];g={i=0;c=count l;while{i<c}do{if(i<count l)then{e=l select i;call _this};i=i+1}};{l=l+call format["V%1",e]}call g;"l=l-[e]+[e];if(count l<c)then{c=count l;i=0}"call g;l}

Ligue para:

hint format
[
    "%1\n%2\n%3\n%4\n%5\n%6\n%7\n%8\n%9",
    [3, [[1, 2], [2, 0]], 1] call f,
    [5, [[0, 2], [0, 3], [1, 2]], 3] call f,
    [6, [[0, 3], [1, 3], [2, 4], [5, 1]], 4] call f,
    [6, [[0, 3], [1, 3], [2, 4], [5, 1]], 5] call f,
    [5, [[0, 1], [2, 0], [0, 3], [4, 0]], 2] call f,
    [6, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]], 3] call f,
    [4, [[0, 1], [1, 2], [2, 0]], 3] call f,
    [5, [[0, 2], [2, 4]], 2] call f,
    [8, [], 7] call f
]

Resultado:

Desenrolado:

f =
{
    t = _this;
    r = t select 1;
    i = 0;
    while {i < t select 0} do
    {
        call format["V%1=[%1]", i];
        i = i + 1
    };

    i = 0;
    while {i < count r} do
    {
        call format(["V%1=V%1+V%2;V%2=V%1"] + (r select i));
        i = i + 1
    };

    l = call format["V%1", t select 2];

    g =
    {
        i = 0;
        c = count l;
        while {i < c} do
        {
            if (i < count l) then
            {
                e = l select i;
                call _this
            };
            i = i + 1
        }
    };

    {l = l + call format["V%1", e]} call g;
    "l = l - [e] + [e];

    if (count l<c)then
    {
        c = count l;
        i = 0
    }" call g;

    l
}

Python 2 , 53 bytes

e,s,n=input()
b={s}
for p in n*e:b|=b&p and p
print b

Experimente online!

Mesmo comprimento que a função:

lambda e,s,n:reduce(lambda b,p:b|(b&p and p),n*e,{s})

Experimente online!

Isso se baseia na boa solução de Rod usando a atualização de curto-circuito b|=b&p and p. Tomar o número de variáveis ​​como entrada najuda a diminuir o código do loop.

Geléia ,  12   11  10 bytes

-1 graças a Erik the Outgolfer (substitua o átomo œ&por f)

⁹fÐfȯFµÐLQ

Um link diádico aceitando Eà esquerda (como uma lista de comprimento-duas-listas) e Sà direita (como número inteiro) retornando uma lista [desduplicada].

Experimente online! ou veja uma suíte de testes .

Quão?

⁹fÐfȯFµÐLQ - Link: list of lists, E; integer S
      µÐL  - repeat the monadic chain to the left until a fixed point is reached:
  Ðf       -   (for each pair in E) filter keep if:
 f         -     filter discard if in
⁹          -     chain's right argument
           -     (originally [S], thereafter the previous result as monadic)
    ȯ      -   logical OR with implicit right
           -   (force first pass to become S if nothing was kept)
     F     -   flatten to a single list
           -   (S -> [S] / [[1,4],[1,0]]->[1,4,1,0] / etc...)
         Q - de-duplicate

Perl 5 -n0 , 49 39 bytes

Dê o valor inicial em uma linha em STDIN seguido por linhas de pares de números equivalentes (ou dê o valor inicial por último ou no meio ou dê vários valores iniciais, tudo funciona)

#!/usr/bin/perl -n0
s/
$1? | $1/
/ while/^(\d+
)/msg;say//g

Experimente online!

Isso pode gerar um elemento no conjunto de resultados várias vezes. Essa variação de 48 bytes gera cada elemento equivalente apenas uma vez:

s/
$1? | $1/
/ while/^(\d+
)(?!.*^\1)/msg;say//g

Experimente online!

Ruby , 39 bytes

->e,*s{e.map{e.map{|a|a-s!=a&&s|=a}};s}

Experimente online!

K (ngn / k) , 37 36 35 bytes

{&a[z]=a:{y[x]&:|y x;y}[+y,,&2]/!x}

Experimente online!

{ }função com argumentos x, y, e zrepresentando N, Ee Srespectivamente

!x é a lista 0 1 ... x-1

&2 é a lista 0 0

y,,&2nós adicionamos o par 0 0para yevitar o caso especial de um vazioy

+y,,&2 mesma coisa transposta de uma lista de pares para um par de listas

{ }[+y,,&2]é uma projeção, ou seja, uma função na qual xserá o valor +y,,&2e yserá o argumento passado ao chamar a projeção

|y xestá ynos índices x, invertido ( |)

@[y;x;&;|y x]alterar os yíndices, xutilizando o mínimo ( &) do elemento existente e um elemento de|y x

/ continue ligando até convergência

a: atribuir a um

a[z]=zmáscara booleana dos elementos aigual a z-th

& converte a máscara booleana em uma lista de índices

Oitava , 48 45 bytes

t=@(A,u)find(((eye(size(A))+A+A')^nnz(A))(u,:));

Recebe entrada como "adjacency-matrix", por exemplo, usa [0 0 0; 0 0 1; 1 0 0]para [2 = 3, 3 = 1], experimente online!

Explicação

Primeiro, construímos a matriz de adjacência completa para o gráfico transitivo, usando a soma de eye(size(A))(elementos são reflexivos), A(entrada) eA' (a relação é simétrica).

Calculamos o fechamento transitivo computando o poder de nnz(A)que é suficiente ( nnz(A)é limite superior para o comprimento de um caminho), então a partir daí tudo o que resta é fazer com que a linha direita com (u,:)e findtodas as entradas diferentes de zero.

Python 2 , 87 bytes

g,v=input();x={v};d=[v]
for c in d:x|={c};d+={k[k[0]==c]for k in g if c in k}-x
print x

Experimente online!

Pari / GP , 80 bytes

f(g,p)=c=concat;if(p==q=c(c(p=Set(p),[e|e<-g,setintersect(Set(e),p)])),p,f(g,q))

Experimente online!

JavaScript (ES6), 87 bytes

(a,n)=>a.map(([b,c])=>[...d[b]||[b],...d[c]||[c]].map((e,_,a)=>d[e]=a),d=[])&&d[n]||[n]

A desduplicação seria possível usando &&[...new Set(d[n]||[n])]a um custo de 14 bytes.