Contar os ciclos terminais de um gráfico direcionado

8

Tarefa

Você deve escrever um programa ou função no idioma de sua escolha, que conte com precisão o número de ciclos de terminal de um gráfico direcionado simples.

Esse tipo específico de gráfico direcionado é representado como uma matriz de n números inteiros, cada um com um valor aleatório escolhido independentemente entre 1 e n (ou 0 e n-1, se o seu idioma conta com 0). O gráfico pode ser visto como setas apontando de um índice (nó) para um índice que corresponda ao valor encontrado no índice inicial.

Sua função deve ser capaz de aceitar gráficos grandes, até n = 1024, ou qualquer tamanho inteiro menor.

Exemplo

Considere este gráfico para n = 10:

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

O índice 1 contém um 9, então há uma seta do índice 1 para o índice 9. O índice 9 contém um 6, então há uma seta 9 -> 6. O índice 6 contém 6, que é um ciclo terminal, apontando de volta para si mesmo.

O Índice 2 contém um 7. O Índice 7 contém um 3. O Índice 3 contém um 8. O Índice 8 contém um 10. O Índice 10 contém um 8, portanto esse é um segundo ciclo terminal (8 -> 10 -> 8 -> 10, etc. )

Índice 4 -> 10, que entra no segundo ciclo do terminal. Da mesma forma, o índice 5 -> 2 -> 7 -> 3 -> 8, que também faz parte do segundo ciclo do terminal.

Nesse ponto, todos os índices (nós) foram verificados, todos os caminhos foram seguidos e dois ciclos terminais únicos foram identificados. Portanto, a função deve retornar 2 , pois esse é o número de ciclos de terminal neste gráfico direcionado.

Pontuação

Aponte para o menor código, mas verifique se ele conta os ciclos do terminal corretamente. O código mais curto após 1 semana vence.

Casos de teste

Aqui estão alguns casos de teste para verificar a correção do seu código. Se o seu idioma conta índices de matriz a partir de 0, é claro que você deve subtrair 1 do valor de cada elemento da matriz, para evitar um índice fora de limite.

n = 32, 5 ciclos:

[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 ciclos:

[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 ciclos:

[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 ciclos:

[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 ciclo:

[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 ciclo:

[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 ciclos:

[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]
fosgênio
fonte
Claro, aqui está um grande caso de teste n = 1024. Espero que não o tenha massacrado enquanto o empacotava para o Stack Exchange.
phosgene
Esclarecer: se o idioma usar matrizes baseadas em zero, os números na matriz serão todos baseados em zero, ou não?
Ypnypn
Sim esta correto. Os números na matriz sempre apontam para um índice de matriz válido. Eu usei o método de contagem de 'estilo humano' para começar com 1, porque é isso que minha linguagem usa e não queria estragar meus exemplos.
phosgene

Respostas:

2

GolfScript, 25 caracteres

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

A mesma abordagem da solução de Keith Randall , mas no GolfScript. Observe que o GolfScript possui matrizes com índice zero. Testador 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
fonte
Difícil de acreditar que muito é realizado com tão pouco código.
DavidC 5/05
Isso é impressionantemente curto.
phosgene
5

Mathematica 69

Código

Este encontra o número de componentes do gráfico.

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

O primeiro caso de teste:

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


Análise

Faça uma lista de arestas direcionadas entre índices (usando o exemplo 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 -> 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 desenha um gráfico mostrando os componentes do gráfico.

ImagePaddinge VertexLabels são usados ​​aqui para mostrar os índices.

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

componentes

WeaklyConnectedComponents retorna a lista de vértices para cada componente.

Length retorna o número de componentes.

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


Tempo da lista de amostras com 1024 elementos:

Tempo: 0.002015 seg

f[z] // AbsoluteTiming

{0,002015, 6}


Apenas por diversão, aqui está uma imagem do caso de teste final, representado graficamente. Omiti os rótulos dos vértices; existem muitos.

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

gráfico z

DavidC
fonte
1
Muito conciso, apesar do nome da função de 25 caracteres. Isso pode ser difícil de bater. Além disso, parece uma história de Escolha sua própria aventura.
phosgene
WeaklyConnectedComponentsé muito detalhado. Mas dá muito trabalho. (Nunca se deve subestimar J e linguagens semelhantes por concisão.) #
187
Em algum momento, suspeito que o Wolfram fique sem ideias e apenas comece a transformar as respostas do Stack Exchange em funções de biblioteca, para justificar novos lançamentos.
phosgene 5/05
Sim, entendo o que você quer dizer. Atualmente, existem literalmente milhares de funções incorporadas ao Mathematica. O estranho é que eles trabalham juntos tão bem.
DavidC 5/05
Essa estrutura inicial de reescrita de expressões foi uma boa ideia. Agora, se ao menos eles implementassem vários níveis de desfazer ... #
6135
2

Python, 132 116 caracteres

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)

Para cada índice, seguimos arestas para n hops, o que garante que estamos em um ciclo terminal. Seguimos n mais saltos e encontramos o índice mínimo nesse ciclo. O número total de ciclos de terminal é apenas o número de mínimos diferentes que encontramos.

Keith Randall
fonte
Eu gosto deste método Talvez haja uma maneira de combinar 'i em r' loops?
phosgene
Triste que você não pode #define F for i in r, em Python, C (++) - estilo ... :)
tomsmeding
1

Em 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]])
user2228078
fonte
1
Isso é código-golfe. Por favor, adicione o número de bytes no seu envio. Você pode remover espaços em branco desnecessários.
Martin Ender
1
Bem como parênteses desnecessários. Eles não são necessários nas ifcondições.
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]])é melhor: 102 bytes.
Mayıʇǝɥʇuʎs 5/05
1

J - 61 53 char

Este foi um doozy.

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

A <@<:transformar a lista em um gráfico de J, que se parece com uma lista de caixas, ea caixa no índice icontém todos os nós que nó ise conecta. J indexa de zero, então usamos <:para diminuir tudo um por um antes de encaixar <.

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

O <~.@(],;@:{~)^:_&.>]transforma cada nó em uma lista de todos os nós que podem ser alcançadas a partir dele. Ele <...&.>]é responsável por fazer isso acontecer com cada nó e, na ~.@(],;@:{~)^:_verdade, vem de um J golfe dessa tarefa de 'nós alcançáveis' que fiz algumas semanas atrás.

   (<~.@(],;@:{~)^:_&.>])@:(<@<:) 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.executa uma tarefa interessante. Se o fechamento de "alcançabilidade" do gráfico (a versão do gráfico, de modo que se houver arestas direcionadas X → Y e Y → Z, adicionarmos a aresta X → Z.) Tiver N nós e arestas E, e.nesse gráfico uma matriz booleana de N linhas e colunas E, com um True se o nó correspondente compartilhar um nó acessível com essa borda. Confuso, mas tenha paciência comigo.

   ([: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

Em seguida, temos que encontrar o número de ciclos de terminal, ou seja, o número de grupos que compartilham Trues entre suas colunas. Queremos fazer uma espécie de tabela de multiplicação das linhas ( "1/~) e usamos um tipo de produto interno como a multiplicação, aquela que ANDs em pares e depois ORs todos os resultados juntos ( +./ .*). A matriz resultante é uma tabela quadrada com um True em cada posição em que duas linhas compartilham pelo menos uma coluna entre elas.

   ([:+./ .*"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

Agora tudo o que precisamos fazer é verificar quantos tipos diferentes de padrões de linha existem. Portanto, fazemos exatamente isso: agrupe linhas do mesmo tipo ( /.~), relate o número em cada grupo ( #) e, em seguida, pegue o número de grupos ( #@).

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

Uso em outros exemplos:

   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

Infelizmente, o gabinete do elemento 1024 agora leva muito tempo para terminar. A versão anterior <:@#@((#~0={.+/@:*"1])^:a:)@e.@(~.@(],;@:{~)^:_&.>~<)@:(<@<:)(61 caracteres) levou um pouco mais de um segundo para fazer isso.

algoritmshark
fonte
Ah sim, o bom e velho e. função, eu deveria saber. o_O Estou começando a olhar para o seu código. Bem feito.
phosgene
0

Python (96)

Muito, muito, muito, muito com base na resposta do usuário2228078, pois funciona exatamente da mesma forma, mas é mais eficiente:

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

(Pergunta técnica: o golfe de outra pessoa deve ser um wiki da comunidade?)

ɐɔıʇǝɥʇuʎs
fonte
Você tem a minha bênção para plagiar. Que seja um esforço da comunidade.
phosgene 5/05
@ user2790167 Claro, aí está;)
ɐɔıʇǝɥʇuʎs 5/05
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

A idéia principal é começar em cada nó à vez e percorrer o caminho a partir dele, marcando cada nó que visitamos com um rótulo exclusivo para o nó em que começamos. Se alguma vez atingirmos um nó marcado, paramos de andar e verificamos se a marcação é a que corresponde ao nosso nó inicial. Se for, devemos ter percorrido um loop, então aumentamos a contagem de ciclos em um.

No código, ué o contador de ciclo, ié o nó inicial, jé o nó atual em que estamos andando. O rótulo correspondente ao nó inicial ié seu complemento de bit ~ique é sempre negativo. Marcamos um nó apontando-o para esse valor, substituindo o que ele realmente apontou (tomando cuidado para caminhar até esse nó antes que ele seja esquecido).

Sabemos que atingimos um nó marcado quando caminhamos para um "nó" de valor negativo imediatamente depois. Verificamos se esse valor negativo é o rótulo atual para ver se percorremos um ciclo. Como cada nó que andamos é efetivamente excluído, cada ciclo será percorrido apenas uma vez.

Ele salva caracteres para contar i manualmente com uma variável dummy loop e _depois como for i in range(len(G)). As listas Python são indexadas em 0. Se eles fossem indexados em 1, poderíamos salvar dois caracteres escrevendo j=i=i+1para ter ie jser 1 no primeiro loop e escrever j>0no lugar de j>=0.

Editar:

Podemos salvar dois caracteres iterando isobre os elementos da lista em vez dos índices, pois o nó que não é apontado por nenhuma borda não importa. Temos que repetirset(G)Porém, para evitar a repetição de um nó inicial apontado por vários outros nós.

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
xnor
fonte
O código Python mais curto já publicado, e um método interessante de 'marcação de giz'. Eu gosto disso.
phosgene