from time import clock import sys def bfs(matrix): que=[] list=[] visit=[0,0,0,0,0] v=3 list.append(chr(v+64)) visit.insert(v-1,1) que.append(v) while que: v=que.pop(0) for i in range(0,6): if( matrix[v-1][i]==1 and visit[i]==0): #print i+1 #print chr(i+65) list.append(chr(i+65)) visit[i]=1 que.append(i+1) fout.write("-".join(list)) def main(): global fout '''matrix = [[0] * 6 for i in xrange(6)] matrix=[[0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,1,1,0],[0,1,1,0,1,1],[0,0,1,1,0,1],[0,0,0,1,1,0]] print matrix''' start = clock() fin=open("in18_8.txt","r") fout=open("out_28_18_8.txt","w") def mat(n): matrix=[] for i in range(n): matrix.append([]) return matrix m=0 count=0 for x in fin: if count==0: list=x.split(",") n=int(list[0]) matrix=mat(n) else: list1=x.split(",") for j in list1: matrix[count-1].append(int(j)) count+=1 bfs(matrix) end = clock() time= end - start fout.write("\n\n Total execuion time ="+ str(time)+ " seconds") m=m+sys.getsizeof(matrix)+sys.getsizeof(list)+sys.getsizeof(list1)+sys.getsizeof(x)+sys.getsizeof(fin)+sys.getsizeof(fout) fout.write("\n Memory used= "+str(m)+" bytes") fin.close() fout.close() main()