Hi,
I submitted my solution to CABLETV, and got NZEC error. I tested my prog with some test cases, and it works fine. Anybody can give me any hints to fix my prog? Thanks a lot.
# SPOJ Problem Set (classical)
# 300. Cable TV Network
# Problem code: CABLETV
def is_connected(g):
"""
detect whether an undirected graph is connected. dfs is used to traverse a sub-graph of g: if the sub-graph has the same number of vertex as g, g is connected.
argument:
g: 2d array for adjacency list representation.
return:
true if g is connected; otherwise, false.
"""
color = []
for v in g:
color.append('white')
c = 0;
for i, v in enumerate(g):
if color[i] == 'white':
c += is_connected_visit(color, i, g)
break
return c == len(g)
def is_connected_visit(color, u, g):
"""
sub-function used by is_connected(g).
argument:
color: the array that maps vertex and its state (white: unvisited; gray: depth-first visiting; black: visited.)
u: the vertex is going to be visited.
g: the graph.
return:
true if the graph g is connected; otherwise, false.
"""
color[u] = 'gray'
c = 1
for v in g[u]:
if color[v] == 'white':
c += is_connected_visit(color, v, g)
color[u] = 'black'
return c
def matrix_g(g):
"""
complete the edge information for graph g. Input graph information is not always complete. For example, (u, v) is input while (v, u) not. this function will supplement vertex adjacency information.
argument:
g: the 2d array representing a graph.
return:
the 2d array containing complete vertex adjacency information.
"""
for i, v in enumerate(g):
for w in v:
if i not in g[w]:
g[w].append(i)
return g
def next(bs):
"""
sub-function used by select(g). use binary-string method to generate the next element when calculating power set. the function is destructive.
argument:
bs: a binary string representing the current subset. this argument may be modified.
return:
true if the next subset is constructed; false if no such item left.
"""
c = len(bs)
for b in bs[::-1]:
c -= 1
if b == 0:
break
if c > 0 or (c == 0 and bs[0] == 0):
bs[c] = 1
for i in range(c + 1, len(bs)):
bs[i] = 0
return True
else:
return False
def select(g):
"""
generate the power set over the vertex set of g.
argument:
g: the 2d array representing a graph.
return:
the power set over the vertex set of g.
"""
r =[]
bs = [0] * len(g)
while next(bs):
z = []
for i, b in enumerate(bs):
if b == 1:
z.append(i)
r.append(z)
return r
def remove(s, g):
"""
generate a new graph that removes vertex set s from g.
argument:
s: the vertex set element of which will be removed from g.
g: the 2d array representing a graph.
return:
a 2d array representing graph that does not contain vertexes in s.
"""
a = len(g)
b = len(s)
r = [[] for i in range(a - b)]
m = {}
c = 0
for i in range(a):
if i not in s:
m[i] = c
c += 1
for v, vn in enumerate(g):
if v not in s:
for w in vn:
if w not in s and m[w] not in r[m[v]]:
r[m[v]].append(m[w])
return r
def fac(g):
"""
calculate the network's safty factor.
argument:
g: a 2d array representing a graph.
return:
the network g's sfaty factor.
"""
if not is_connected(g) or len(g) == 0:
return 0
else:
q = select(g)
for s in q:
g2 = remove(s, g)
if not is_connected(g2) or len(g2) == 0:
return len(s)
def calc():
"""
entry function of the solution.
"""
n = int(raw_input('input network numbers: '))
r = []
for i in range(n):
test = raw_input('input a network: ').split()
gvn = int(test[0])
gen = int(test[1])
g = [[] for v in range(gvn)]
for e in range(2, 2 + gen):
edge = test[e].split(',')
edge[0] = int(edge[0].replace('(', ''))
edge[1] = int(edge[1].replace(')', ''))
g[edge[0]].append(edge[1])
g[edge[1]].append(edge[0])
matrix_g(g)
r.append(fac(g))
for f in r:
print f
calc()
# testing
# g = [[1, 2], [0, 2, 4], [], [], [], [4], [1, 3, 5]]
# matrix_g(g)
# print g
# print is_connected(g)
# bs = [0, 0, 1, 0, 1, 1, 1]
# next(bs)
# print bs
# print '-' * 16
# g2 = [0, 1, 2, 3]
# print select(g2)
# print g
# g3 = remove([2], g)
# print g3
# print fac(g)
# e1 = [[1, 2], [0, 2], [0, 1]]
# e2 = [[], []]
# e3 = [[1, 2], [0, 2, 3, 4], [0, 1, 3], [1, 2, 4], [1, 3]]
# print fac(e1)
# print fac(e2)
# print fac(e3)
