최종순위 (위상정렬)

indegree[x] 가 0인 노드들을 순서대로 넣어주고 만약 큐가 비게된다면 cycle이 발생한 것, 큐의 사이즈가 2개이상이라면 경로가 2개이상인 개수가 발생한다는 것입니다.

 

from collections import deque

 

t = int(input())

 

while t:

    n = int(input())

    indegree = [0]*(n+1)

 

    graph = [[False]*(n+1) for _ in range(n+1)]

    datas = list(map(int,input().split()))

    

    for i in range(n):

        for j in range(i+1,n):

            graph[datas[i]][datas[j]]=True

            indegree[datas[j]]+=1

 

    m = int(input())

    for i in range(m):

        a, b= map(int,input().split())

        if graph[a][b]==True:

            graph[a][b]=False

            graph[b][a]=True

            indegree[a]+=1

            indegree[b]-=1

        else:

            graph[b][a]=False

            graph[a][b]=True

            indegree[b]+=1

            indegree[a]-=1

 

    result = []

    q = deque()    

    

    for i in range(1,n+1):

        if indegree[i] == 0:

            q.append(i)

    

    certain = True

    cycle = False

 

    for i in range(n):

        if len(q) == 0:

            cycle = True

            break

        if len(q)>=2:

            certain = False

            break

        now = q.popleft()

        result.append(now)

        for j in range(1,n+1):

            if graph[now][j]:

                indegree[j]-=1

                if indegree[j] == 0:

                    q.append(j)

    if cycle:

        print("IMPOSSIBLE")

    elif not certain:

        print("?")

    else:

        for i in result:

            print(i, end=' ')

        print()        

    t-=1