pengantar
Dalam tantangan ini, Anda diberi grafik terarah dengan loop otomatis, dan tugas Anda adalah mengonversinya menjadi grafik tidak terarah tanpa loop otomatis.
Memasukkan
Input Anda adalah grafik terarah dengan set simpul {0, 1, ..., n-1}
untuk sejumlah bilangan asli n ≥ 0
(atau {1, 2, ..., n}
jika Anda menggunakan pengindeksan berbasis 1). Grafik diberikan sebagai n
daftar panjang di L
mana L[i]
adalah daftar tetangga vertex i
. Misalnya, daftar [[0,1],[0],[1,0,3],[]]
mewakili grafik
.-.
| v
'-0<--2-->3
^ |
| |
v |
1<--'
Perhatikan bahwa daftar tetangga tidak perlu dipesan, tetapi mereka dijamin bebas duplikat.
Keluaran
Output Anda adalah grafik lain dalam format yang sama dengan input, diperoleh dari itu sebagai berikut.
- Hapus semua loop otomatis.
- Untuk setiap tepi yang tersisa
u -> v
, tambahkan tepi terbalikv -> u
jika belum ada.
Seperti halnya input, daftar tetangga dari grafik output mungkin tidak berurutan, tetapi mereka tidak dapat berisi duplikat. Untuk grafik di atas, output yang benar adalah [[1,2],[0,2],[0,1,3],[2]]
, yang mewakili grafik
0<->2<->3
^ ^
| |
v |
1<--'
Aturan
Anda dapat menggunakan pengindeksan berbasis-0 atau berbasis-1 dalam grafik. Fungsi dan program lengkap dapat diterima. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Uji Kasus
Kasus uji ini menggunakan pengindeksan berbasis 0; menambah setiap angka dalam kasus berbasis 1. Daftar tetangga ini diurutkan dalam urutan menaik, tetapi tidak diperlukan.
[] -> []
[[0]] -> [[]]
[[],[0,1]] -> [[1],[0]]
[[0,1],[]] -> [[1],[0]]
[[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]]
[[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]]
[[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
[[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
[[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
[[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]
.e
baru saja beralih darik,Y
kek,b
, jadi untuk menjalankan ini, gunakan.e-.|f}k@QTUQbkQ
CJam,
4340353433 byte2 byte disimpan oleh Sp3000.
Ini dimulai sebagai solusi yang sangat elegan dan kemudian semakin mengerikan ketika saya mencoba memperbaiki beberapa lubang yang saya abaikan. Saya belum yakin apakah ide aslinya masih dapat diselamatkan, tetapi saya akan mencoba yang terbaik ...
Uji di sini. Atau, jalankan seluruh test harness .
Saya akan menambahkan penjelasan setelah saya yakin pasien sudah mati.
sumber
Python 2, 107 byte
Masih berusaha mencari tahu apakah saya bisa bermain golf lebih banyak, tetapi untuk sekarang, ini adalah yang terbaik yang bisa saya lakukan.
Saya menggunakan set untuk mencegah duplikat; juga, tidak seperti
list.remove(i)
,{S}-{i}
tidak membuat kesalahan jikai
tidak adaS
.sumber
Ruby, 78 byte
Akhirnya beberapa digunakan untuk operator set Ruby (
[1,2]&[2]==[2]
dan[3,4,5]-[4]==[3,5]
).ideone , termasuk semua test case, yang dilaluinya.
sumber
CJam, 26 byte
Tidak terlalu pendek ...
Penjelasan
sumber
JavaScript (ES6), 96
110Membuat set adjacency dari daftar adjacency, yang membantu menghindari duplikat. Iklan terakhir membangun kembali daftar mulai dari set.
sumber
Jawa, 150
Kode diperluas, dapat dijalankan:
sumber
Groovy - 87
Script lengkap untuk menjalankan tes:
sumber
Mathematica,
846664 byteMenggunakan pengindeksan berbasis 1.
sumber
Python 3, 127 byte
Coba online
Bukan usaha terbaik saya ...
sumber