Tantangan

Program Anda harus mengambil 3 input:

• Integer positif yang merupakan jumlah variabel,
• Satu set pasangan bilangan bulat non-negatif yang tidak berurutan, di mana masing-masing pasangan mewakili kesetaraan antara variabel, dan
• Integer positif yang mewakili variabel awal,

Ini harus mengembalikan satu set bilangan bulat non-negatif yang mewakili semua variabel yang dapat ditunjukkan sama secara transitif dengan variabel awal (termasuk variabel awal itu sendiri).

Dengan kata lain, diberikan masukan N, Edan S, kembali set Q, sehingga:

• S ∈ Q.
• Jika Z ∈ Qdan (Y = Z) ∈ Ekemudian Y ∈ Q.
• Jika Z ∈ Qdan (Z = Y) ∈ Ekemudian Y ∈ Q.

Ini juga dapat dinyatakan sebagai masalah teori grafik :

Diberikan grafik tak berarah dan sebuah simpul dalam grafik, daftar simpul dalam komponen yang terhubung .

Spesifikasi

• Anda dapat memilih untuk menggunakan pengindeksan berbasis-0 atau berbasis-1.
• Input pertama menghitung jumlah variabel yang ada, di mana variabel diberikan sebagai angka. Atau, Anda tidak dapat mengambil input ini, dalam hal ini diasumsikan sama dengan indeks variabel tertinggi yang ada, atau satu lebih dari ini, tergantung pada skema pengindeksan Anda.
• Anda dapat mengasumsikan input terbentuk dengan baik: Anda tidak akan diberikan variabel di luar rentang yang ditentukan oleh input pertama. Misalnya, 3, [1 = 2, 2 = 0], 1adalah input yang valid, sedangkan 4, [1 = 719, 1 = 2, 3 = 2], -3tidak.
• Anda tidak dapat berasumsi bahwa variabel apa pun akan memiliki persamaan yang terkait dengannya. Jika diberi input ketiga yang "kesepian" (tidak memiliki persamaan), output yang benar adalah satu set tunggal yang hanya berisi input tersebut (karena sama dengan dirinya sendiri).
• Anda dapat mengasumsikan bahwa persamaan tidak akan mengandung kesetaraan dari variabel ke variabel itu sendiri, dan bahwa kesetaraan yang sama tidak akan diberikan beberapa kali (ini termasuk hal-hal seperti 1 = 2dan 2 = 1).
• Anda dapat mengasumsikan bahwa semua bilangan bulat yang diberikan akan berada dalam jangkauan representatif bahasa Anda.
• Anda dapat mengambil input kedua dalam format apa pun yang masuk akal.

Berikut beberapa format yang masuk akal:

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]

• Anda dapat menampilkan dalam format apa pun yang wajar (mis. Set, daftar, dll.). Ketertiban tidak relevan.

Mencetak gol

Ini adalah kode-golf , sehingga program terpendek yang valid (dalam byte) menang.

Kasus Uji (0-diindeks)

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}

Kasus Uji (1-diindeks)

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 byte

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

Cobalah online!

Penjelasan

{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 byte

^{-2 bytes terima kasih kepada ovs}

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

Cobalah online!

Pyth , 12 byte

u|sf@TGQG.{E

Suite uji.

Bersih , 85 81 byte

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

Cobalah online!

Menentukan fungsi $ :: [[Int]] -> ([Int] -> [Int])

Bahasa Wolfram (Mathematica) , 32 byte

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

Masukkan format: {2<->3, 3<->1}, 3 . Tidak mengambil input pertama.

Cobalah online!

Operasi bahasa skrip Flashpoint , 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}

Telepon dengan:

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
]

Keluaran:

Belum dibuka:

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 byte

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

Cobalah online!

Panjang yang sama dengan fungsi:

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

Cobalah online!

Ini didasarkan pada solusi bagus Rod menggunakan pembaruan hubungan arus pendek b|=b&p and p. Mengambil jumlah variabel sebagai input nmembantu mempersingkat kode loop.

Jelly ,  12   11  10 byte

-1 berkat Erik the Outgolfer (ganti atom œ&dengan f)

⁹fÐfȯFµÐLQ

Tautan diad menerima Edi sebelah kiri (sebagai daftar panjang-dua-daftar) dan Sdi sebelah kanan (sebagai bilangan bulat) mengembalikan daftar [de-duplikat].

Cobalah online! atau lihat test-suite .

Bagaimana?

⁹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 byte

Berikan nilai awal pada garis pada STDIN diikuti oleh garis pasangan angka yang setara (atau berikan nilai awal terakhir atau di tengah atau berikan beberapa nilai awal, semuanya bekerja)

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

Cobalah online!

Ini dapat menampilkan elemen dalam hasil yang disetel beberapa kali. Variasi 48 byte ini menghasilkan setiap elemen yang setara hanya sekali:

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

Cobalah online!

Ruby , 39 byte

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

Cobalah online!

K (ngn / k) , 37 36 35 byte

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

Cobalah online!

{ }fungsi dengan argumen x, ydan zmewakiliN , Edan Smasing-masing

!x adalah daftar 0 1 ... x-1

&2 adalah daftarnya 0 0

y,,&2kami menambahkan pasangan 0 0key menghindari kasus khusus kosongy

+y,,&2 hal yang sama dialihkan dari daftar pasangan ke pasangan daftar

{ }[+y,,&2]adalah proyeksi, yaitu fungsi yang xakan menjadi nilai+y,,&2 dan yakan menjadi argumen yang dilewatkan ketika memanggil proyeksi

|y xada ydi indeksx , terbalik ( |)

@[y;x;&;|y x]mengubah yindeks xdengan mengambil minimum (& ) dari elemen yang ada dan elemen dari|y x

/ terus menelepon sampai konvergensi

a: ditugaskan untuk a

a[z]=ztopeng boolean dari elemen asama denganz -th

& mengonversi topeng boolean ke daftar indeks

Oktaf , 48 45 byte

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

Mengambil input sebagai "adjacency-matrix", misalnya penggunaan [0 0 0; 0 0 1; 1 0 0]untuk [2 = 3, 3 = 1], coba online!

Penjelasan

Pertama kita membangun matriks adjacency lengkap untuk grafik transitif, menggunakan jumlah eye(size(A))(elemen refleksif), A(input) dan A'(hubungannya simetris).

Kami menghitung penutupan transitif dengan menghitung kekuatan nnz(A)yang mencukupi ( nnz(A)adalah batas atas untuk panjang lintasan), jadi dari sana semua yang tersisa adalah untuk mendapatkan baris kanan dengan (u,:)dan findsemua entri bukan nol.

Python 2 , 87 byte

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

Cobalah online!

Pari / GP , 80 byte

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

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

Deduplikasi akan dimungkinkan menggunakan &&[...new Set(d[n]||[n])]biaya 14 byte.