Hitung siklus terminal dari grafik yang diarahkan

8

Tugas

Anda harus menulis sebuah program atau fungsi dalam bahasa pilihan Anda yang secara akurat menghitung jumlah siklus terminal dari grafik sederhana yang diarahkan.

Jenis grafik terarah khusus ini direpresentasikan sebagai array n bilangan bulat, masing-masing dengan nilai acak yang dipilih secara independen antara 1 dan n (atau 0 dan n-1, jika bahasa Anda dihitung dari 0). Grafik dapat dianggap sebagai panah yang menunjuk dari satu indeks (simpul) ke indeks yang cocok dengan nilai yang ditemukan pada indeks awal.

Fungsi Anda harus mampu menerima grafik besar, hingga n = 1024, atau ukuran integer yang lebih kecil.

Contoh

Pertimbangkan grafik ini untuk n = 10:

[9, 7, 8, 10, 2, 6, 3, 10, 6, 8]

Indeks 1 berisi 9, jadi ada panah dari indeks 1 ke indeks 9. Indeks 9 berisi 6, jadi ada panah 9 -> 6. Indeks 6 berisi 6, yang merupakan siklus terminal, menunjuk kembali ke dirinya sendiri.

Indeks 2 berisi 7. Indeks 7 berisi 3. Indeks 3 berisi 8. Indeks 8 berisi 10. Indeks 10 berisi 8, jadi itu adalah siklus terminal kedua (8 -> 10 -> 8 -> 10, dll. ).

Indeks 4 -> 10, yang memasuki siklus terminal kedua. Demikian juga, indeks 5 -> 2 -> 7 -> 3 -> 8, yang juga merupakan bagian dari siklus terminal kedua.

Pada titik ini, semua indeks (node) telah diperiksa, semua jalur telah diikuti, dan dua siklus terminal yang unik diidentifikasi. Oleh karena itu, fungsi harus mengembalikan 2 , karena itu adalah jumlah siklus terminal dalam grafik yang diarahkan ini.

Mencetak gol

Bidik kode terkecil, tetapi pastikan ia menghitung siklus terminal dengan benar. Kode terpendek setelah 1 minggu menang.

Uji Kasus

Berikut adalah beberapa kasus uji untuk memeriksa kebenaran kode Anda. Jika bahasa Anda menghitung indeks array mulai dari 0, tentu saja Anda harus mengurangi 1 dari nilai setiap elemen array, untuk mencegah indeks out-of-bound.

n = 32, 5 siklus:

[8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32]

n = 32, 4 siklus:

[20, 31, 3, 18, 18, 18, 8, 12, 25, 10, 10, 19, 3, 9, 18, 1, 13, 5, 18, 23, 20, 26, 16, 22, 4, 16, 19, 31, 21, 32, 15, 22]

n = 32, 3 siklus:

[28, 13, 17, 14, 4, 31, 11, 4, 22, 6, 32, 1, 13, 15, 7, 19, 10, 28, 9, 22, 5, 26, 17, 8, 6, 13, 7, 10, 9, 30, 23, 25]

n = 32, 2 siklus:

[25, 23, 22, 6, 24, 3, 1, 21, 6, 18, 20, 4, 8, 5, 16, 10, 15, 32, 26, 25, 27, 14, 13, 12, 9, 9, 29, 8, 13, 31, 32, 1]

n = 32, 1 siklus:

[6, 21, 15, 14, 22, 12, 5, 32, 29, 3, 22, 23, 6, 16, 20, 2, 16, 25, 9, 22, 13, 2, 19, 20, 26, 19, 32, 3, 32, 19, 28, 16]

n = 32, 1 siklus:

[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, 6, 7]

n = 1024, 6 siklus:

[239, 631, 200, 595, 178, 428, 582, 191, 230, 551, 223, 61, 564, 463, 568, 527, 143, 403, 154, 236, 928, 650, 14, 931, 236, 170, 910, 782, 861, 464, 378, 748, 468, 779, 440, 396, 467, 630, 451, 130, 694, 167, 594, 115, 671, 853, 612, 238, 464, 771, 825, 471, 167, 653, 561, 337, 585, 986, 79, 506, 192, 873, 184, 617, 4, 259, 4, 662, 623, 694, 859, 6, 346, 431, 181, 703, 823, 140, 635, 90, 559, 689, 118, 117, 130, 248, 931, 767, 840, 158, 696, 275, 610, 217, 989, 640, 363, 91, 129, 399, 105, 770, 870, 800, 429, 473, 119, 908, 481, 337, 504, 45, 1011, 684, 306, 126, 215, 729, 771, 5, 302, 992, 380, 824, 868, 205, 807, 917, 407, 759, 181, 640, 685, 795, 258, 180, 900, 20, 773, 546, 866, 564, 761, 632, 895, 968, 980, 651, 225, 676, 18, 685, 784, 208, 227, 3, 267, 852, 57, 487, 566, 633, 849, 309, 543, 145, 575, 811, 621, 560, 492, 24, 665, 66, 851, 168, 262, 259, 754, 481, 565, 768, 172, 1012, 241, 3, 370, 985, 389, 82, 779, 744, 829, 836, 249, 975, 909, 840, 226, 867, 499, 192, 909, 972, 735, 252, 785, 545, 486, 186, 1011, 89, 939, 649, 110, 119, 185, 836, 717, 545, 938, 621, 946, 94, 363, 721, 177, 747, 59, 819, 146, 283, 821, 547, 654, 941, 755, 18, 449, 367, 499, 944, 62, 553, 435, 344, 900, 25, 251, 920, 902, 99, 326, 98, 495, 385, 929, 865, 327, 725, 674, 33, 173, 429, 873, 558, 90, 460, 366, 543, 583, 954, 792, 213, 536, 670, 49, 738, 802, 1015, 23, 915, 119, 263, 307, 601, 474, 971, 826, 613, 446, 37, 145, 894, 901, 307, 906, 886, 990, 89, 798, 384, 487, 822, 354, 768, 902, 163, 179, 134, 920, 439, 619, 215, 94, 709, 744, 366, 543, 349, 347, 2, 438, 141, 486, 19, 998, 500, 857, 955, 932, 1, 587, 195, 646, 550, 887, 626, 400, 348, 154, 808, 678, 873, 186, 282, 168, 993, 722, 56, 345, 5, 226, 328, 22, 894, 658, 264, 13, 803, 791, 359, 217, 997, 168, 578, 952, 734, 964, 898, 659, 628, 980, 15, 31, 439, 13, 875, 687, 1004, 1023, 165, 642, 561, 897, 711, 124, 404, 346, 723, 774, 352, 784, 276, 395, 14, 443, 343, 153, 510, 590, 172, 215, 130, 106, 295, 906, 133, 758, 483, 898, 391, 760, 702, 972, 721, 611, 592, 1001, 724, 934, 59, 831, 171, 253, 869, 431, 538, 20, 648, 76, 351, 103, 33, 385, 852, 437, 470, 95, 434, 408, 430, 994, 366, 706, 809, 532, 161, 388, 668, 245, 965, 365, 913, 471, 927, 245, 256, 805, 540, 380, 995, 446, 657, 545, 573, 955, 499, 322, 949, 635, 401, 185, 421, 626, 534, 429, 930, 633, 563, 348, 626, 518, 682, 233, 775, 444, 42, 199, 57, 271, 683, 397, 883, 620, 768, 8, 331, 497, 19, 340, 900, 919, 497, 276, 78, 252, 164, 764, 927, 242, 270, 759, 824, 945, 886, 262, 59, 439, 217, 720, 519, 862, 626, 326, 339, 589, 16, 565, 947, 604, 144, 87, 520, 256, 240, 336, 685, 361, 998, 805, 678, 24, 980, 203, 818, 855, 85, 276, 822, 183, 266, 347, 8, 663, 620, 147, 189, 497, 128, 357, 855, 507, 275, 420, 755, 131, 469, 672, 926, 859, 156, 127, 986, 489, 803, 433, 622, 951, 83, 862, 108, 192, 167, 862, 242, 519, 574, 358, 549, 119, 630, 60, 925, 414, 479, 330, 927, 94, 767, 562, 919, 1011, 999, 908, 113, 932, 632, 403, 309, 838, 341, 179, 708, 847, 472, 907, 537, 516, 992, 944, 615, 778, 801, 413, 653, 690, 393, 452, 394, 596, 545, 591, 136, 109, 942, 546, 57, 626, 61, 587, 862, 829, 988, 965, 781, 849, 843, 815, 60, 928, 784, 388, 341, 491, 565, 83, 110, 164, 38, 1024, 859, 297, 520, 327, 733, 699, 631, 78, 178, 671, 895, 818, 637, 99, 425, 933, 248, 299, 333, 144, 323, 105, 849, 942, 767, 265, 72, 204, 547, 934, 916, 304, 919, 273, 396, 665, 452, 423, 471, 641, 675, 60, 388, 97, 963, 902, 321, 826, 476, 782, 723, 99, 735, 893, 565, 175, 141, 70, 918, 659, 935, 492, 751, 261, 362, 849, 593, 924, 590, 982, 876, 73, 993, 767, 441, 70, 875, 640, 567, 920, 321, 46, 938, 377, 905, 303, 736, 182, 626, 899, 512, 894, 744, 254, 984, 325, 694, 6, 367, 532, 432, 133, 938, 74, 967, 725, 87, 502, 946, 708, 122, 887, 256, 595, 169, 101, 828, 696, 897, 961, 376, 910, 82, 144, 967, 885, 89, 114, 215, 187, 38, 873, 125, 522, 884, 947, 962, 45, 585, 644, 476, 710, 839, 486, 634, 431, 475, 979, 877, 18, 226, 656, 573, 3, 29, 743, 508, 544, 252, 254, 388, 873, 70, 640, 918, 93, 508, 853, 609, 333, 378, 172, 875, 617, 167, 771, 375, 503, 221, 624, 67, 655, 465, 272, 278, 161, 840, 52, 1016, 909, 567, 544, 234, 339, 463, 621, 951, 962, 1019, 383, 523, 279, 780, 838, 984, 999, 29, 897, 564, 762, 753, 393, 205, 31, 150, 490, 156, 796, 586, 676, 773, 465, 489, 1024, 433, 214, 701, 480, 604, 280, 241, 563, 943, 911, 12, 400, 261, 883, 999, 207, 618, 141, 959, 767, 978, 461, 992, 982, 272, 143, 404, 645, 331, 348, 783, 698, 827, 82, 145, 536, 449, 852, 750, 789, 413, 913, 420, 14, 499, 285, 533, 223, 75, 591, 994, 884, 237, 63, 411, 563, 611, 801, 173, 759, 278, 318, 772, 1018, 48, 440, 333, 611, 834, 423, 583, 22, 716, 393, 794, 83, 83, 864, 859, 600, 525, 808, 569, 95, 952, 852, 567, 651, 2, 984, 906, 992, 747, 602, 143, 547, 1008, 940, 245, 633, 378, 193, 771, 965, 648, 437, 873, 591, 664, 271, 777, 274, 742, 68, 429, 825, 144, 55, 272, 279, 6, 400, 485, 66, 311, 663, 441, 23, 988, 726, 48, 624, 302, 617, 120, 653, 810, 641, 142]
fosgen
sumber
Tentu, inilah kasus besar n = 1024 tes. Mudah-mudahan saya tidak memotongnya saat mengemasnya untuk Stack Exchange.
phosgene
Klarifikasi: Jika bahasa menggunakan array berbasis nol, maka angka-angka dalam array semua akan berbasis nol, atau tidak?
Ypnypn
Ya itu benar. Angka-angka dalam array akan selalu mengarah ke indeks array yang valid. Saya menggunakan metode penghitungan 'gaya manusia' mulai dari 1 karena itulah yang digunakan bahasa saya, dan saya tidak ingin mengacaukan contoh saya.
phosgene

Jawaban:

2

GolfScript, 25 karakter

:I{{I=.}I.+,*]I,>$0=}%.&,

Pendekatan yang sama seperti solusi Keith Randall tetapi dalam GolfScript. Perhatikan bahwa GolfScript memiliki array yang diindeks nol. Penguji online .

:I        # Assign input to variable I
{         # Foreach item in I
  {I=.}   # Code block: take the n-th list item
  I.+,*   # Iterate the code block 2*len(I) times
  ]       # and gather result in an array
  I,>     # Take last len(I) items
  $0=     # Get minimum
}%
.&        # Take unique items
,         # Count
Howard
sumber
Sulit dipercaya begitu banyak yang dicapai dengan kode yang begitu sedikit.
DavidC
Itu sangat singkat.
phosgene
5

Mathematica 69

Kode

Ini menemukan jumlah komponen grafik.

f@l_ := Length@WeaklyConnectedComponents@Graph@Thread[Range@Length@l -> l]

Kasus uji pertama:

v = {8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32}
f[v]

5


Analisis

Buat daftar tepi terarah di antara indeks, (menggunakan contoh 1).

Thread[Range@Length@v -> v

{1 -> 8, 2 -> 28, 3 -> 14, 4 -> 8, 5 -> 2, 6 -> 1, 7 -> 13, 8 -> 15, 9 -> 30, 10 -> 30, 10 -> 17 , 11 -> 9, 12 -> 8, 13 -> 18, 14 -> 19, 15 -> 30, 16 -> 3, 17 -> 8, 18 -> 25, 19 -> 23, 20 -> 12 , 21 -> 6, 22 -> 7, 23 -> 19, 24 -> 24, 25 -> 17, 26 -> 7, 27 -> 21, 28 -> 20, 29 -> 29, 30 -> 15 , 31 -> 32, 32 -> 32}


Graph menggambar grafik yang menunjukkan komponen grafik.

ImagePaddingdan VertexLabels digunakan di sini untuk menampilkan indeks.

Graph[Thread[Range[Length@v] -> v], ImagePadding -> 30, VertexLabels -> "Name"]

komponen

WeaklyConnectedComponents mengembalikan daftar simpul untuk setiap komponen.

Length mengembalikan jumlah komponen.

c = WeaklyConnectedComponents[g]
Length[c]

{{17, 10, 25, 8, 18, 1, 4, 12, 15, 13, 6, 20, 30, 7, 21, 28, 9, 22, 26, 27, 2, 11, 5}, { 14, 3, 19, 16, 23}, {32, 31}, {24}, {29}}

5


Waktu daftar sampel dengan 1024 elemen:

Pengaturan waktu: 0,002015 dtk

f[z] // AbsoluteTiming

{0,002015, 6}


Hanya untuk bersenang-senang, inilah gambar kasus ujian akhir, yang dibuat gambarnya. Saya menghilangkan label titik; terlalu banyak.

Graph[Thread[Range[Length@z] -> z], GraphLayout -> "RadialEmbedding"]

grafik z

DavidC
sumber
1
Sangat ringkas, meski memiliki nama fungsi 25 karakter. Ini mungkin sulit dikalahkan. Selain itu, ini terlihat seperti kisah Choose Your Own Adventure.
phosgene
WeaklyConnectedComponentssangat verbose. Tapi itu banyak pekerjaan. (Seseorang seharusnya tidak pernah meremehkan bahasa J dan bahasa-bahasa serupa untuk keringkasan.)
DavidC
Pada titik tertentu, saya curiga Wolfram akan kehabisan ide dan mulai mengubah jawaban Stack Exchange menjadi fungsi perpustakaan, untuk membenarkan rilis baru.
phosgene
Ya, saya mengerti maksud Anda. Ada ribuan fungsi yang dibangun ke dalam Mathematica saat ini. Yang aneh adalah mereka bekerja sama dengan baik.
DavidC
Kerangka awal penulisan ulang ekspresi itu adalah ide bagus. Sekarang seandainya mereka menerapkan beberapa tingkat undo ...
phosgene
2

Python, 132 116 karakter

def T(V):
 n=len(V);r=range(n);s={}
 for i in r:
    p=[i]
    for k in r+r:p+=[V[p[-1]]]
    s[min(p[n:])]=1
 return len(s)

Untuk setiap indeks, kami mengikuti tepian untuk n hop, yang menjamin kami berada dalam siklus terminal. Kami kemudian mengikuti n lebih banyak lompatan dan menemukan indeks minimum dalam siklus itu. Jumlah total siklus terminal adalah jumlah minimum yang berbeda yang kita temukan.

Keith Randall
sumber
Saya suka metode ini. Mungkin ada cara untuk menggabungkan loop 'i in r'?
phosgene
Sedih karena Anda tidak dapat #define F for i in rmenggunakan Python, C (++) - style ... :)
tommeding
1

Dengan Python:

def c(l):
    if(l==[]):
        return 0
    elif (l[-1]==len(l)):
        return c(l[:-1])+1
    else:
        return c([[x,l[-1]][x==len(l)] for x in l[:-1]])
pengguna2228078
sumber
1
Ini adalah kode-golf. Harap tambahkan jumlah byte dalam kiriman Anda. Anda mungkin ingin menghapus spasi yang tidak perlu.
Martin Ender
1
Serta kurung yang tidak perlu. Mereka tidak dibutuhkan dalam ifkondisi.
user12205
c=lambda l:0 if l==[] else c(l[:-1])+1 if l[-1]==len(l) else c([[x,l[-1]][x==len(l)] for x in l[:-1]])lebih baik: 102 byte.
5ıʇǝɥʇu
1

J - 61 53 char

Yang ini doozy.

#@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:)

The <@<:mengubah daftar ke grafik J, yang terlihat seperti daftar kotak, dan kotak pada indeks iberisi semua node node imenghubungkan ke. Indeks J dari nol, jadi kami gunakan <:untuk mengurangi semuanya satu per satu sebelum bertinju <.

   (<@<:) 9 7 8 10 2 6 3 10 6 8
+-+-+-+-+-+-+-+-+-+-+
|8|6|7|9|1|5|2|9|5|7|
+-+-+-+-+-+-+-+-+-+-+

The <~.@(],;@:{~)^:_&.>]berubah setiap node menjadi daftar semua node yang dapat dicapai dari itu. Yang <...&.>]bertanggung jawab untuk membuat ini terjadi pada setiap node, dan ~.@(],;@:{~)^:_sebenarnya berasal dari J golf dari tugas 'node terjangkau' yang saya lakukan beberapa minggu yang lalu.

   (<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
+---+-------+---+---+---------+-+-----+---+-+---+
|8 5|6 2 7 9|7 9|9 7|1 6 2 7 9|5|2 7 9|9 7|5|7 9|
+---+-------+---+---+---------+-+-----+---+-+---+

e.melakukan tugas yang menarik. Jika "reachability" penutupan grafik (versi grafik sedemikian rupa sehingga jika ada tepi terarah X → Y dan Y → Z kita tambahkan edge X → Z.) Memiliki N node dan E edge, maka e.pada grafik ini membuat matriks boolean dari N baris dan kolom E, dengan True jika node yang sesuai berbagi node yang dapat dijangkau dengan tepi ini. Membingungkan, tapi tahan dengan saya

   ([:e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1

Selanjutnya, kita harus menemukan jumlah siklus terminal, yaitu jumlah grup yang membagikan Trues di antara kolom mereka. Kami ingin membuat semacam tabel perkalian dari baris ( "1/~), dan kami menggunakan jenis produk dalam sebagai perkalian, yang dipasangkan dengan AND dan kemudian ATAU semua hasil secara bersamaan ( +./ .*). Matriks yang dihasilkan adalah tabel persegi dengan True di setiap posisi yang dua baris berbagi setidaknya satu kolom di antara mereka.

   ([:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1

Sekarang yang tersisa untuk dilakukan adalah memeriksa berapa banyak jenis pola baris yang ada. Jadi kami melakukan hal itu: kelompokkan baris bersama-sama dari jenis yang sama ( /.~), laporkan angka di setiap grup ( #), lalu ambil jumlah grup ( #@).

   #@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
2

Penggunaan pada contoh lain:

   tcc =: #@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:)  NB. name
   tcc 8 28 14 8 2 1 13 15 30 17 9 8 18 19 30 3 8 25 23 12 6 7 19 24 17 7 21 20 29 15 32 32
5
   tcc 20 31 3 18 18 18 8 12 25 10 10 19 3 9 18 1 13 5 18 23 20 26 16 22 4 16 19 31 21 32 15 22
4
   tcc 6 21 15 14 22 12 5 32 29 3 22 23 6 16 20 2 16 25 9 22 13 2 19 20 26 19 32 3 32 19 28 16
1
   tcc tentwentyfour  NB. the 1024-node example
6

Sayangnya kasus elemen 1024 sekarang membutuhkan waktu yang sangat lama untuk diakhiri. Versi sebelumnya <:@#@((#~0={.+/@:*"1])^:a:)@e.@(~.@(],;@:{~)^:_&.>~<)@:(<@<:)(61 char) butuh sedikit lebih dari satu detik untuk melakukan ini.

algoritme hiu
sumber
Ah ya, si tua yang baik. fungsi, saya seharusnya tahu. o_O Saya mulai sering melihat kode Anda. Sudah selesai dilakukan dengan baik.
phosgene
0

Python (96)

Sangat, sangat, sangat, sangat berdasarkan pada jawaban user2228078, karena kerjanya persis sama, tetapi lebih golf:

c=lambda l:(1+c(l[:-1])if l[-1]==len(l)else c([[x,l[-1]][x==len(l)]for x in l[:-1]]))if l else 0

(Pertanyaan teknis: haruskah golf jawaban orang lain menjadi komunitas wiki?)

ɐɔıʇǝɥʇu
sumber
Anda memiliki berkah saya untuk menjiplak. Biarkan itu menjadi upaya komunitas.
phosgene
@ user2790167 Tentu, ini dia;)
ɐɔıʇǝɥʇuʎ
0

Python (89) (87)

def c(G):
 u=i=0
 for _ in G:
  j=i;i+=1
  while j>=0:G[j],j=~i,G[j]
  u+=j==~i
 return u

Gagasan utamanya adalah memulai pada setiap simpul secara bergantian dan berjalan di sepanjang jalan dari sana, menandai setiap simpul yang kita kunjungi dengan label unik ke simpul yang kita mulai. Jika kita pernah mengenai simpul yang ditandai, kita berhenti berjalan, dan memeriksa apakah yang menandai itu sesuai dengan simpul awal kita. Jika itu adalah kita harus berjalan satu lingkaran, jadi kita menambah hitungan siklus satu per satu.

Dalam kode, u adalah penghitung siklus, iadalah simpul awal, jadalah simpul saat ini yang kami lewati. Label yang sesuai dengan starting node iadalah komplemen bitnya ~iyang selalu negatif. Kami menandai sebuah simpul dengan mengarahkannya ke nilai itu, menimpa simpul apa pun yang sebenarnya ditunjuknya (berhati-hati untuk berjalan ke simpul itu sebelum dilupakan).

Kami tahu kami telah mencapai simpul yang ditandai ketika kami berjalan ke "simpul" bernilai negatif segera setelahnya. Kami memeriksa apakah nilai negatif itu adalah label saat ini untuk melihat apakah kami telah menjalani siklus. Karena setiap simpul yang kita berjalan dihapus secara efektif, setiap siklus hanya akan berjalan satu kali.

Menghemat karakter untuk menghitung isecara manual dengan variabel dummy loop _lalu sebagai for i in range(len(G)). Daftar python diindeks 0. Jika mereka bukan 1-diindeks, kita dapat menyimpan dua karakter dengan menulis j=i=i+1untuk dimilikii dan jmenjadi 1 untuk loop pertama, dan menulis j>0di tempat j>=0.

Edit:

Kita dapat menyimpan dua karakter dengan mengulangi ielemen-elemen dalam daftar daripada indeks, karena simpul yang tidak ditunjukkan oleh sisi mana pun tidak masalah. Kita harus mengulanginya terlebih dahulu set(G)untuk menghindari pengulangan simpul awal yang ditunjukkan oleh beberapa simpul lainnya.

def c(G):
 u=0
 for i in set(G):
  j=i
  while j>=0:G[j],j=~i,G[j]
  u+=j==~i
 return u
Tidak
sumber
Kode Python terpendek yang diposting, dan metode 'penandaan kapur' yang menarik. Saya suka itu.
phosgene