Language: C++


n, m, q = gets.split.map(&:to_i)

prob = {}
(1..m).each do
    i, j = gets.split.map(&:to_i) 
    (prob[i] ||= Hash.new(1.0))[j] = q / 100.0
    (prob[j] ||= Hash.new(1.0))[i] = q / 100.0
end

require 'set'

def f(prob)
    return 1.0 if prob.size == 1

    if prob.size == 1 + prob.values.map(&:size).inject(:+) / 2
        return prob.keys.combination(2).map {|i, j| prob[i].key?(j) ? 1 - prob[i][j] : 1}.inject(:*)
    end

    i = prob.keys.min_by{|i| prob[i].size}
    j = prob[i].keys.min_by{|j| prob[j].size}

    new_prob = {}
    prob.each {|k, h| new_prob[k] = h.dup}
    new_prob[i].delete(j)
    new_prob[j].delete(i)

    
    reached = disconnected?(new_prob)
    if reached
        g1 = {}
        new_prob.each {|k, h| g1[k] = new_prob[k].dup if reached.include?(k)}
        g2 = {}
        new_prob.each {|k, h| g2[k] = new_prob[k].dup if !reached.include?(k)}
        return (1.0 - prob[i][j]) * f(g1) * f(g2)
    else
        return prob[i][j] * f(new_prob) + (1.0 - prob[i][j]) * f(contract(prob, i, j))
    end
end

def contract(prob, i, j)
    new_prob = {}
    new_prob[j] = prob[j].dup
    new_prob[j].delete(i)
    prob.each do |k, h|
        next if k == i or k == j
        new_prob[k] = h.dup
        q = h[i]
        new_prob[k].delete(i)
        new_prob[k][j] *= q
        new_prob[j][k] = new_prob[k][j]
    end
    new_prob
end

require 'set'
def disconnected?(prob)
    i = prob.keys[0]
    reached = Set[i]
    queue = [i]
    until queue.empty?
        i = queue.shift
        prob[i].each do |j, _|
            next if reached.include?(j)
            reached << j
            queue << j
        end
    end
    return reached.size == prob.size ? nil : reached
end

if disconnected?(prob)
    puts '0'
else
    printf("%.12f\n", f(prob))
end



Compiler output:
a.cc:5:2: error: too many decimal points in number
    5 | (1..m).each do
      |  ^~~~
a.cc:11:9: warning: multi-character character constant [-Wmultichar]
   11 | require 'set'
      |         ^~~~~
a.cc:56:9: warning: multi-character character constant [-Wmultichar]
   56 | require 'set'
      |         ^~~~~
a.cc:2:1: error: 'n' does not name a type
    2 | n, m, q = gets.split.map(&:to_i)
      | ^
a.cc:5:2: error: expected unqualified-id before numeric constant
    5 | (1..m).each do
      |  ^~~~
a.cc:5:2: error: expected ')' before numeric constant
    5 | (1..m).each do
      | ~^~~~
      |  )
a.cc:17:90: error: expected unqualified-id before '.' token
   17 |         return prob.keys.combination(2).map {|i, j| prob[i].key?(j) ? 1 - prob[i][j] : 1}.inject(:*)
      |                                                                                          ^
a.cc:21:5: error: 'j' does not name a type
   21 |     j = prob[i].keys.min_by{|j| prob[j].size}
      |     ^
a.cc:23:5: error: 'new_prob' does not name a type
   23 |     new_prob = {}
      |     ^~~~~~~~
a.cc:24:5: error: 'prob' does not name a type
   24 |     prob.each {|k, h| new_prob[k] = h.dup}
      |     ^~~~
a.cc:25:5: error: 'new_prob' does not name a type
   25 |     new_prob[i].delete(j)
      |     ^~~~~~~~
a.cc:32:9: error: 'new_prob' does not name a type
   32 |         new_prob.each {|k, h| g1[k] = new_prob[k].dup if reached.include?(k)}
      |         ^~~~~~~~
a.cc:33:9: error: 'g2' does not name a type
   33 |         g2 = {}
      |         ^~
a.cc:34:9: error: 'new_prob' does not name a type
   34 |         new_prob.each {|k, h| g2[k] = new_prob[k].dup if !reached.include?(k)}
      |         ^~~~~~~~
a.cc:35:9: error: expected unqualified-id before 'return'
   35 |         return (1.0 - prob[i][j]) * f(g1) * f(g2)
      |         ^~~~~~
a.cc:43:5: error: 'new_prob' does not name a type
   43 |     new_prob[j] = prob[j].dup
      |     ^~~~~~~~