Dua simpul berbeda dalam grafik berarah sangat terhubung jika ada jalur dalam grafik dari satu sama lain. Sebuah komponen sangat terhubung dari grafik adalah bagian dari grafik sehingga setiap pasangan simpul yang berbeda dalam subset sangat terhubung, dan menambahkan lagi simpul untuk subset akan mematahkan properti ini.
Tantangan Anda adalah memisahkan grafik menjadi komponen-komponennya yang sangat terhubung. Khususnya, Anda harus menampilkan semua SCC dalam grafik.
I / O:
Sebagai input, Anda dapat menggunakan daftar tepi terarah, daftar adjacency, matriks adjacency, atau format input wajar lainnya. Tanyakan apakah Anda tidak yakin. Anda dapat mengasumsikan grafik tidak memiliki simpul yang benar-benar terputus, dan bahwa tidak ada tepi sendiri, tetapi Anda tidak dapat membuat asumsi lebih lanjut. Anda juga dapat secara opsional mengambil daftar simpul sebagai input, serta jumlah simpul.
Sebagai output, Anda harus memberikan partisi simpul, seperti daftar daftar simpul, di mana setiap sublist adalah komponen yang sangat terhubung, atau pelabelan simpul, di mana setiap label sesuai dengan komponen yang berbeda.
Jika Anda menggunakan pelabelan, label harus berupa simpul, atau urutan bilangan bulat berturut-turut. Ini untuk mencegah penghancuran komputasi ke dalam label.
Contoh:
Contoh-contoh ini mengambil daftar tepi, di mana setiap tepi diarahkan dari entri 1 ke entri kedua, dan partisi keluaran. Anda bebas menggunakan format ini atau yang lain.
Input ada di baris pertama, output ada di baris kedua.
[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]
[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]
[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]
[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]
Penilaian dan pembatasan:
Celah standar dilarang, seperti biasa. Juga, built-in yang khusus menangani komponen yang sangat terhubung dilarang.
Solusi harus berjalan dalam waktu tidak lebih dari satu jam pada contoh yang diberikan. (Ini dimaksudkan untuk mencegah solusi eksponensial lambat, dan tidak ada yang lain.)
Ini kode golf. Bytes paling sedikit menang.
sumber
8
tidak ada dalam komponen dengan[3,4]
karena tidak bisa hanya masing6
- masing dan7
tidak ada yang mencapai itu.Jawaban:
Python 2 menggunakan numpy,
7162 byteMengambil input sebagai
numpy
matriks yang mewakili kedekatan dan jumlah node. Menghasilkan output sebagainumpy
matriks baris yang memberi label setiap simpul dengan nomor simpul terendah di komponennya.Untuk matriks adjacency
M
, kekuatan matriksM**n
menghitung jumlahn
lintasan -step dari setiap titik awal ke setiap titik ujung. Menambahkan identitas keM
viaM+M**0
memodifikasi matriks adjacency untuk menambahkan loop diri ke setiap sisi. Jadi,(M+M**0)**n
hitung jalur panjang paling banyakn
(dengan redundansi).Karena setiap jalur memiliki panjang paling banyak
n
, jumlah node, di(i,j)
mana titikj
dapat dicapai darii
sesuai dengan entri positif(M+M**0)**n
. Matriks reachability kemudianR=(M+M**0)**n>0
, di mana>0
bekerja secara masuk akal.Menghitung entrywise
and
sebagaiR&R.T
, di manaR.T
adalah transpos, kemudian memberikan matriks yang menunjukkan pasangan dari simpul yang dapat dicapai bersama. Inii
baris th merupakan vektor indikator untuk simpul dalam komponen sangat terhubung sama seperti. Mengambilargmax
dari setiap barisnya memberikan indeks yang pertamaTrue
di dalamnya, yang merupakan indeks dari simpul terkecil dalam komponennya.sumber
JavaScript (ES6), 125 byte
Mengambil daftar pasangan terarah sebagai argumen, sementara hasilnya adalah array untuk setiap simpul yang memberikan simpul pertama sangat terhubung, yang saya percaya dianggap sebagai pelabelan yang valid. Misalnya, dengan input
[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
yang dikembalikan[, 1, 1, 3, 3, 1, 6, 6, 3]
(tidak ada titik 0; titik 1, 2 dan 5 memiliki label 1; 3, 4 dan 8 memiliki label 3 sedangkan 6 dan 7 memiliki label 6).sumber
MATL ,
2622 byteIni menggunakan pendekatan yang sama dengan jawaban @ xnor .
Bekerja dalam versi bahasa saat ini (15.0.0) .
Input adalah matriks kedekatan dari grafik, dengan baris yang dipisahkan oleh titik koma. Kasus uji pertama dan terakhir adalah
Cobalah online!
sumber
Pyth, 13 byte
Demonstrasi , Test suite
Input adalah daftar adjacency, direpresentasikan sebagai kamus yang memetakan simpul ke daftar simpul yang memiliki tepi (tetangga yang diarahkan). Output adalah partisi.
Inti dari program ini adalah kita menemukan kumpulan simpul yang dapat dijangkau dari masing-masing simpul, dan kemudian mengelompokkan simpul dengan set tersebut. Setiap dua simpul dalam SCC yang sama memiliki kumpulan simpul yang sama yang dapat dijangkau darinya, karena masing-masing simpul dapat dijangkau dari yang lain, dan keterjangkauan bersifat transitif. Setiap simpul dalam komponen yang berbeda memiliki set yang dapat dijangkau yang berbeda, karena masing-masing set tidak mengandung yang lain.
Penjelasan kode:
sumber