O meu algoritmo usa estes mesmos princípios: backtracking e pontes. Eu gero todos os 2^m conjuntos de arestas possíveis e o único prunning que eu uso é cortar subconjuntos com (estritamente) menos de n arestas, isso é óbvio, é ímpossivel ter um grafo biconexo com menos de n arestas.
Acho que a única coisa que vale a pena ser comentada tem a ver com forma como eu implementei o backtracking. A idéia geral também é bem padrão, considerar a bijeção entre cada subconjunto e a representação em binários de [0, 2^m), o jeito padrão de implementar isso seria algo como:
max = 2^m -1; for (i = 0; i <= max; i++) { q = max; num = i; for (j = 0; j < m; j++) { bool[j] = num / q; num = num % q; q = q / 2; } }
Onde cada posição do vetor booleano bool representa um elemento. Eu fiz um teste com essa implementação, consegui AC com um tempo de 641MS. Uma forma como eu implentei inicialmente foi:
max = 2^m -1; for (i = 0; i <= max; i++) { for (j = 0; j < m; j++) bool[j] = (i & (1 << j)) == 0 ? 0 : 1; }
Essa forma não é tão evidente, é um pouco mais enxuta, mas principalmente é MUITO mais rápida, usando essa implementação o tempo caiu para 94MS, acontece que operações bit a bit são muito mais rápidas do que divisões.
Nesse caso, ambas forma conseguem AC, mas em outro problema o tempo limite pode não ser tão assim tão folgado. Acho que isso é uma coisa bastante simples, aplicavel a um número grande de problemas de backtracking e, principalmente, pode significar uma economia de tempo não desprezivel.
Isso pode não ser novidade pra muita gente, pra esses, mal ae por ficar floodando o wiki… :-)
