Wyzwanie

Twój program powinien przyjąć 3 dane wejściowe:

• Dodatnia liczba całkowita, która jest liczbą zmiennych,
• Zestaw nieuporządkowanych par nieujemnych liczb całkowitych, gdzie każda para reprezentuje równość między zmiennymi, i
• Dodatnia liczba całkowita reprezentująca zmienną początkową,

Powinien zwrócić zestaw nieujemnych liczb całkowitych, które reprezentują wszystkie zmienne, które mogą być tranzytowo równe zmiennej początkowej (w tym samej zmiennej początkowej).

Innymi słowy, wprowadzone dane N, Eoraz S, zwraca zestaw Q, tak że:

• S ∈ Q.
• Jeśli Z ∈ Qi (Y = Z) ∈ Ewtedy Y ∈ Q.
• Jeśli Z ∈ Qi (Z = Y) ∈ Ewtedy Y ∈ Q.

Można to również wyrazić jako problem teorii grafów :

Biorąc pod uwagę niekierowany wykres i wierzchołek na wykresie, wypisz listę wierzchołków w jego połączonym składniku .

Dane techniczne

• Możesz wybrać indeksowanie oparte na 0 lub na podstawie 1.
• Pierwsze wejście zlicza liczbę obecnych zmiennych, przy czym zmienne są podawane jako liczby. Alternatywnie, nie możesz wziąć tych danych wejściowych, w którym to przypadku zakłada się, że jest on równy albo najwyższemu obecnemu indeksowi zmiennych, albo o jeden większy, w zależności od twojego schematu indeksowania.
• Możesz założyć, że dane wejściowe są dobrze sformułowane: nie otrzymasz zmiennych poza zakresem określonym przez pierwsze dane wejściowe. Na przykład 3, [1 = 2, 2 = 0], 1jest poprawnym wejściem, a 4, [1 = 719, 1 = 2, 3 = 2], -3nie jest.
• Nie można zakładać, że dowolna zmienna będzie z nią powiązana. Jeśli podano trzecie wejście, które jest „samotne” (nie ma równości), poprawnym wyjściem jest zestaw singletonów zawierający tylko to wejście (ponieważ jest ono równe sobie).
• Możesz założyć, że równości nie będą zawierały równości między zmienną a samą, i że ta sama równość nie zostanie podana wiele razy (obejmuje to takie jak 1 = 2i 2 = 1).
• Możesz założyć, że wszystkie podane liczby całkowite będą w reprezentatywnym zakresie dla twojego języka.
• Drugie wejście możesz pobrać w dowolnym rozsądnym formacie.

Oto kilka rozsądnych formatów:

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]

• Możesz wyprowadzać dane w dowolnym rozsądnym formacie (np. Zestaw, lista itp.). Porządek jest nieistotny.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy prawidłowy program (w bajtach).

Przypadki testowe (indeksowane 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}

Przypadki testowe (indeksowane 1)

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}

Brachylog , 22 bajty

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

Wypróbuj online!

Wyjaśnienie

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

^{-2 bajty dzięki ovs}

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

Wypróbuj online!

Pyth , 12 bajtów

u|sf@TGQG.{E

Zestaw testowy.

Czysty , 85 81 bajtów

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

Wypróbuj online!

Definiuje funkcję $ :: [[Int]] -> ([Int] -> [Int])

Wolfram Language (Mathematica) , 32 bajty

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

Format wejściowy: {2<->3, 3<->1}, 3. Nie przyjmuje pierwszego wejścia.

Wypróbuj online!

Operacja Flashpoint język skryptowy , 364 bajty

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}

Zadzwoń z:

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
]

Wynik:

Rozwinięty:

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 bajty

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

Wypróbuj online!

Ta sama długość co funkcja:

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

Wypróbuj online!

Jest to oparte na dobrym rozwiązaniu Rod wykorzystującym aktualizację zwarciową b|=b&p and p. Przyjmowanie liczby zmiennych jako danych wejściowych npomaga skrócić kod pętli.

Galaretka ,  12   11  10 bajtów

-1 dzięki Eryka Outgolfer (zamiast atomu œ&z f)

⁹fÐfȯFµÐLQ

Dyadyczny link akceptujący Epo lewej stronie (jako lista długości dwóch list) i Spo prawej stronie (jako liczba całkowita) zwraca listę [zduplikowaną].

Wypróbuj online! lub zobacz zestaw testowy .

W jaki sposób?

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

Podaj wartość początkową w wierszu na STDIN, a następnie wiersze par równoważnych liczb (lub podaj wartość początkową na końcu lub w środku lub podaj wiele wartości początkowych, wszystko działa)

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

Wypróbuj online!

Może to wygenerować element w zestawie wyników wiele razy. Ta 48-bajtowa odmiana generuje każdy równoważny element tylko raz:

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

Wypróbuj online!

Rubin , 39 bajtów

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

Wypróbuj online!

K (ngn / k) , 37 36 35 bajtów

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

Wypróbuj online!

{ }funkcja z argumentami x, yi zreprezentująca N, Eoraz Sodpowiednio

!x to lista 0 1 ... x-1

&2 jest lista 0 0

y,,&2dodajemy parę, 0 0aby yuniknąć specjalnego przypadku pustegoy

+y,,&2 to samo przeniesiono z listy par na parę list

{ }[+y,,&2]jest rzutowaniem, tj. funkcją, w której xbędzie wartością argumentu przekazanego podczas wywoływania +y,,&2i ybędzie nim

|y xjest yna indeksach x, odwrócony ( |)

@[y;x;&;|y x]zmienić yna indeksach x, biorąc minimum (& ) z istniejącego elementu i elementu z|y x

/ dzwonić do konwergencji

a: przypisać do

a[z]=zmaska ​​boolowska elementów arównychz -tym

& przekonwertować maskę logiczną na listę indeksów

Oktawa , 48 45 bajtów

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

Pobiera dane wejściowe jako „macierz przylegania”, na przykład używa [0 0 0; 0 0 1; 1 0 0]do [2 = 3, 3 = 1], spróbuj online!

Wyjaśnienie

Najpierw konstruujemy pełną macierz przylegania dla grafu przechodniego, używając sumy eye(size(A))(elementy są zwrotne), A(wejściowej) i A'(relacja jest symetryczna).

Obliczamy zamknięcie przechodnie obliczając moc, do nnz(A)której wystarcza ( nnz(A)jest górną granicą długości ścieżki), więc stamtąd pozostaje tylko uzyskanie odpowiedniego wiersza (u,:)i findwszystkich niezerowych wpisów.

Python 2 , 87 bajtów

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

Wypróbuj online!

Pari / GP , 80 bajtów

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

Wypróbuj online!

JavaScript (ES6), 87 bajtów

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

Deduplikacja byłaby możliwa przy użyciu &&[...new Set(d[n]||[n])]kosztu 14 bajtów.