글 읽기 - 위상 정렬.

qkqhxla1 7년 전 0

뭐가 잘못된지 잘 모르겠습니다..... 바로 4%에서 틀렸습니다가 뜨네요.

주석은 다 달아놨구요 잘못 나오는 예제라도 주시면 정말 감사하겠습니다.

import Queue
n,m = map(int,raw_input().split())
adj = [[] for i in xrange(n+1)] #간선
indegree = [0 for i in xrange(n+1)] #노드

for i in xrange(m): #작곡가만큼 입력
    list = map(int,raw_input().split())[1:]
    for j in xrange(len(list)-1):
        adj[list[j]].append(list[j+1]) #간선과
        indegree[list[j+1]] += 1 #노드에 집어넣음. 아래에 print푸시면 확인 가능합니다..
#print adj
#print indegree
pq = Queue.Queue()
for i in xrange(1,n+1):
    if indegree[i]==0: #시작지점이 될만한것들 큐에 넣음
        pq.put(i)

answer = ''
while not pq.empty():
    here = pq.get()
    answer += str(here) #answer변수에 답을 넣어서
    for i in xrange(len(adj[here])): #일반적인 위상정렬
        there = adj[here][i]
        indegree[there] -= 1
        if indegree[there]==0:
            pq.put(there)
if len(answer)==n: #길이가 n과 같으면 출력하고 사이클이 반복되거나 잘 안되면 0 출력
    print '\n'.join(answer)
else:
    print 0

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

문제

문제

출처

ICPC

위상 정렬.

qkqhxla1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말