Как то так:
import sys
global used,color,col,n,relations
def DFS(v):
global used,color,col,n,relations
used[v] = False
color[v] = col
col= col * (-1)
for j in range(n):
if relations[v][j] != 0 and used[j]: DFS(j)
def main(inpFileName,outpFileName):
global used,color,col,n,relations
with open(inpFileName,"r") as fp:
inp = [int(i) for i in fp.read().split()]
outp = open(outpFileName,"w")
n, m = inp[0:2]
relations = [ [0]*n for i in range(n)]
for i in range(m):
x,y = inp[2+i*2:2+(i+1)*2]
relations[x][y] = 1
relations[y][x] = 1
used = [True]*m
col = 1
color = [0]*n
DFS(x)
ability = True
for i in range(n):
for j in range(n):
if (color[i] == color[j]) and (relations[i][j] != 0): ability = False
if ability :
outp.write('YES\r\n')
for i in range(n):
if color[i] == 1 : outp.write(str(i)+"\r\n")
else:
outp.write('NO\r\n')
outp.close()
if __name__ == "__main__":
if len(sys.argv) >= 3:
main(sys.argv[1],sys.argv[2])
else:
print("Usage %s infile outfile"%sys.argv[0])
Я бы конечно переписал без голбалов, но мне лень.