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) ∈ EwtedyY ∈ Q. - Jeśli
Z ∈ Qi(Z = Y) ∈ EwtedyY ∈ 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, a4, [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 = 2i2 = 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}
Piaskownica
—
Esolanging Fruit
Czy możemy zrezygnować z pierwszego wkładu, jeśli chcemy? Myślę, że nie jest konieczne uzyskanie prawidłowego wyniku
—
dylnan
@dylnan "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 jednemu więcej niż to, w zależności od schematu indeksowania. ”(punkt 2 specyfikacji)
—
Esolanging Fruit
Przepraszam, czasami zapominam zakończyć czytanie
—
dylnan
Czy dane wyjściowe mogą zawierać duplikaty? (Mogę twierdzić, że reprezentuje zestaw ...)
—
Ton Hospel
