oving.py

from sys import stdin, stderr
import traceback

adj_mx = [[0,1,1,0,0,0],[0,0,0,1,0,0],[0,0,0,1,1,0],[0,0,0,0,0,1],[0,1,0,1,0,1],[0,0,0,1,0,0]]

class Node():
    def __init__(self, num):
        self.points_to = []
        self.num = num
        self.d = 0
class Queue:
    def __init__(self, lst=[]):
        self.q = []
        self.out = 0
    def push(self, seq):
        self.q.append(seq)
    def pop(self):
        k = self.q[self.out]
        self.out += 1
        return k
    def is_empty(self):
        return self.out == len(self.q)
def create_graph(adj_mx):
    n = len(adj_mx)
    nodes = [Node(i) for i in range(n)] 
    for i in range(n):
        for j in range(n):    
            if adj_mx[i][j] == 1:
                nodes[i].points_to.append(nodes[j])
    return nodes
def bfs(graph, root):
    nodes_found = []
    #for u in graph: u.d = 0    #mark all nodes as undiscovered
    graph[root].d = 1            #mark root node as gray.
    Q = Queue()                #Make a queue, which is empty.
    Q.push(graph[root])        #queue up the root.
    while not Q.is_empty():
        u = Q.pop()
        nodes_found.append(u.num)
        for v in u.points_to:
            if v.d == 0:
                v.d = 1
                Q.push(v)
        u.d = 2
    return nodes_found

def subgraph_density(adj_mx, root):
    graph = create_graph(adj_mx)
    nodes_from_root = bfs(graph, root)
    nodes_from_root.sort(reverse=True)
    subgraph = graph
    for i in nodes_from_root:   #remove any node which is found from root
        #print subgraph
        del subgraph[i]
    num_nodes = len(subgraph)
    num_edges = 0
    #print nodes_from_root
    for node in subgraph:
        for edge in node.points_to:
            if edge.num not in nodes_from_root:
                #print "node:", node, " edge:", edge
                num_edges += 1
    if num_edges == 0:
        return 0
    else:
        return float(num_edges)/float(num_nodes**2)

try:
    n = int(stdin.readline())
    adj_mx = [None] * n # rows
    for i in range(0, n):
        adj_mx[i] = [False] * n # columns
        line = stdin.readline()
        for j in range(0, n):
            adj_mx[i][j] = (line[j] == '1')
    for line in stdin:
        start = int(line)
        print ("%.3f" % (subgraph_density(adj_mx, start) + 1E-12))
except:
    traceback.print_exc(file=stderr)