글 읽기 - 시간초과를 해결할 방법이 있을까요???

dhdbsgn111 5년 전 0

bfs로 거리에 따라서 1,-1로 바꿔가면서 저장하고

다른값이 나올시에는 no를 출력하도록 만들었습니다만

계속해서 시간초과가 발생합니다...

시간을 줄일수 있는 방법이있을까요?

from collections import deque
import sys

def bfs(g,start,c,node):
	dd=[0]*(node+1)
	q=deque()
	q.append(start)
	while q:
		n,p=q.popleft()
		c.append(n)
		if dd[n]==0:
			dd[n]=p
		else:
			if dd[n]!=p:
				return 1,c
			else:
				return 2,c
		fl=list(g[n]-set(c))
		for i in fl:
			q.append((i,p*-1))
	return 2,c		
		
		
if __name__ == "__main__":
	case=int(sys.stdin.readline())
	for i in range(case):
		g={}
		node,line=map(int,sys.stdin.readline().split())
		l=[0]*node
		for j in range(node):
			g[j+1]=[]
		for k in range(line):
			a,b=map(int,sys.stdin.readline().split())
			g[a].append(b)
			g[b].append(a)
		for i in range(1,len(g)+1):
			g[i]=set(g[i])
		ne=1
		c=[]
		while True:
			ans,c=bfs(g,(ne,1),c,node)
			if ans==1:
				print("NO")
				break
			else:
				if len(c)==node:
					print("YES")
					break
				else:
					ne=list(set(range(1,node+1))-set(c))
			
					

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과를 해결할 방법이 있을까요???

dhdbsgn111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말