글 읽기 - 반례를 도저히 모르겠습니다.

kne06201 4년 전 0

틀렸다고 뜨는데 반례를 찾지 못하겠습니다. 반례를 알고싶습니다.

from collections import deque

T = int(input()) #테스트 케이스
for t in range(T):
    seq_flag=0
    sure_flag=0

    # set graph
    n = int(input()) #팀의 수
    indegree = [0]*(n+1)
    node_graph=[[]*(n+1)]
    graph=[[0]*(n+1) for _ in range(n+1)]

    rank = list(map(int, input().split())) #작년 순위
    for i in range(0, n-1):
        for j in range(i+1, n):
            graph[rank[i]][rank[j]]=1

    m = int(input()) #등수 바뀐 쌍의 수

    # change graph with new ranking
    new_rank=[]
    for i in range(m):
        new = list(map(int, input().split()))
        new_rank.append(new)

    for [ni, nj] in new_rank:
        if graph[ni][nj]==1: seq_flag=1
        if graph[nj][ni]==0: seq_flag=1
    for [ni, nj] in new_rank:
        graph[nj][ni]=0
        graph[ni][nj]=1

    # set indegree
    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if graph[i][j]==1: indegree[j]+=1

    queue=deque()
    for i in range(1, n+1):
        if indegree[i]==0: queue.append(i)

    result=[]
    while(queue):
        newi = queue.popleft()
        result.append(newi)
        cnt = 0
        for newj in range(1, n+1):
            if graph[newi][newj]==1:
                indegree[newj]-=1
                if indegree[newj]==0:
                    queue.append(newj)
        cnt+=1
        if cnt>1: sure_flag=1

    if len(result)!=n: seq_flag=1

    if seq_flag==1:
        print('IMPOSSIBLE')
    elif sure_flag==1:
        print('?')
    else:
        for i in result:
            print(i, end=' ')
        print()

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

문제

문제

출처

ICPC

반례를 도저히 모르겠습니다.

kne06201 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말