Die Herausforderung

Ihr Programm sollte 3 Eingaben annehmen:

• Eine positive ganze Zahl, die die Anzahl der Variablen ist,
• Ein Satz ungeordneter Paare nichtnegativer Ganzzahlen, wobei jedes Paar eine Gleichheit zwischen Variablen darstellt
• Eine positive ganze Zahl, die die Startvariable darstellt,

Es sollte eine Menge nichtnegativer Ganzzahlen zurückgeben, die alle Variablen darstellen, von denen gezeigt werden kann, dass sie transitiv gleich der Startvariablen sind (einschließlich der Startvariablen selbst).

Mit anderen Worten, da Eingaben N, Eund Skehren einen Satz Q, so dass:

• S ∈ Q.
• Wenn Z ∈ Qund (Y = Z) ∈ EdannY ∈ Q.
• Wenn Z ∈ Qund (Z = Y) ∈ Edann Y ∈ Q.

Dies kann auch als graphentheoretisches Problem ausgedrückt werden :

Listen Sie bei einem ungerichteten Diagramm und einem Scheitelpunkt im Diagramm die Scheitelpunkte in der zugehörigen verbundenen Komponente auf .

Spezifikationen

• Sie können zwischen einer 0-basierten und einer 1-basierten Indizierung wählen.
• Die erste Eingabe zählt die Anzahl der vorhandenen Variablen, wobei Variablen als Zahlen angegeben werden. Alternativ können Sie diese Eingabe nicht übernehmen. In diesem Fall wird davon ausgegangen, dass sie abhängig von Ihrem Indizierungsschema entweder dem höchsten vorhandenen Variablenindex oder einem höheren entspricht.
• Sie können davon ausgehen, dass die Eingabe wohlgeformt ist: Sie erhalten keine Variablen außerhalb des Bereichs, der durch die erste Eingabe festgelegt wurde. Beispielsweise 3, [1 = 2, 2 = 0], 1ist eine gültige Eingabe, während dies 4, [1 = 719, 1 = 2, 3 = 2], -3nicht der Fall ist.
• Sie können nicht davon ausgehen, dass mit einer Variablen Gleichheiten verknüpft sind. Wenn eine dritte Eingabe "einsam" ist (keine Gleichungen hat), ist die korrekte Ausgabe eine Singleton-Menge, die nur diese Eingabe enthält (da sie sich selbst entspricht).
• Sie können davon ausgehen, dass die Gleichheit keine Gleichheit von einer Variablen zu sich selbst enthält und dass dieselbe Gleichheit nicht mehrmals gegeben wird (dies schließt Dinge wie 1 = 2und ein 2 = 1).
• Sie können davon ausgehen, dass alle angegebenen Ganzzahlen im darstellbaren Bereich Ihrer Sprache liegen.
• Sie können die zweite Eingabe in jedem vernünftigen Format vornehmen.

Hier sind einige sinnvolle Formate:

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]

• Sie können in jedem vernünftigen Format ausgeben (z. B. Set, Liste usw.). Ordnung ist irrelevant.

Wertung

Dies ist Code-Golf , also gewinnt das kürzeste gültige Programm (in Bytes).

Testfälle (0-indiziert)

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}

Testfälle (1-indiziert)

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 Bytes

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

Probieren Sie es online!

Erläuterung

{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 dank ovs}

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

Probieren Sie es online!

Pyth , 12 Bytes

u|sf@TGQG.{E

Testsuite.

Sauber , 85 81 Bytes

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

Probieren Sie es online!

Definiert die Funktion $ :: [[Int]] -> ([Int] -> [Int])

Wolfram Language (Mathematica) , 32 Byte

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

Eingabeformat: {2<->3, 3<->1}, 3. Die erste Eingabe wird nicht übernommen.

Probieren Sie es online!

Operation Flashpoint- Skriptsprache, 364 Byte

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}

Rufen Sie an mit:

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
]

Ausgabe:

Abgerollt:

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

Probieren Sie es online!

Gleiche Länge wie Funktion:

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

Probieren Sie es online!

Dies basiert auf Rods netter Lösung mit dem Kurzschluss-Update b|=b&p and p. Indem Sie die Anzahl der Variablen als Eingabe verwenden n, können Sie den Schleifencode verkürzen.

Jelly ,  12   11  10 Bytes

-1 danke an Erik den Outgolfer (ersetze das Atom œ&durch f)

⁹fÐfȯFµÐLQ

Ein dyadischer Link, der Eauf der linken Seite (als Liste mit Listen mit zwei Längen) und Sauf der rechten Seite (als Ganzzahl) eine [de-duplizierte] Liste zurückgibt.

Probieren Sie es online! oder sehen Sie sich eine Testsuite an .

Wie?

⁹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

Geben Sie den Startwert in einer Zeile in STDIN an, gefolgt von Zeilen mit äquivalenten Zahlenpaaren (oder geben Sie den Startwert zuletzt oder in der Mitte an oder geben Sie mehrere Startwerte an, alles funktioniert).

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

Probieren Sie es online!

Dies kann ein Element in der Ergebnismenge mehrmals ausgeben. Diese 48-Byte-Variation gibt jedes äquivalente Element nur einmal aus:

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

Probieren Sie es online!

Ruby , 39 Bytes

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

Probieren Sie es online!

K (ngn / k) , 37 36 35 Bytes

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

Probieren Sie es online!

{ }Funktion mit Argumenten x, yund zdarstellt N, Eund Sjeweils

!x ist die Liste 0 1 ... x-1

&2 ist die Liste 0 0

y,,&2Wir addieren das Paar 0 0, yum den Sonderfall eines Leerzeichens zu vermeideny

+y,,&2 Das Gleiche wird von einer Liste von Paaren zu einem Paar von Listen übertragen

{ }[+y,,&2]ist eine Projektion, dh eine Funktion, in der xder Wert von +y,,&2und isty das Argument handelt, das beim Aufrufen der Projektion übergeben wird

|y xist ybei Indizes x, umgekehrt ( |)

@[y;x;&;|y x]ändere yan Indizes, xindem &du das Minimum ( ) des existierenden Elements und ein Element aus nimmst|y x

/ ruf weiter an bis zur Konvergenz

a: zuweisen a

a[z]=zBoolesche Maske der Elemente von agleich dem z-ten

& konvertiert die Boolesche Maske in eine Liste von Indizes

Oktave , 48 45 Bytes

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

Nimmt Eingaben als "Adjazenz-Matrix" auf, benutzt zum Beispiel [0 0 0; 0 0 1; 1 0 0]dafür [2 = 3, 3 = 1], probiert es online aus!

Erläuterung

Zuerst konstruieren wir die vollständige Adjazenzmatrix für den transitiven Graphen, wobei wir die Summe aus eye(size(A))(Elemente sind reflexiv), A(Eingabe) und A'(Beziehung ist symmetrisch) verwenden.

Wir berechnen den transitiven Abschluss, indem wir die Potenz berechnen, nnz(A)die ausreicht ( nnz(A)die Obergrenze für die Länge eines Pfades). Von dort müssen wir nur noch die rechte Zeile mit (u,:)und findalle Nicht-Null-Einträge abrufen.

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

Probieren Sie es 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))

Probieren Sie es online!

JavaScript (ES6), 87 Byte

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

Eine Deduplizierung wäre mit &&[...new Set(d[n]||[n])]einem Aufwand von 14 Byte möglich.