[Python]위상정렬 백준 3665

   문제

   https://www.acmicpc.net/problem/3665

순위를 간선으로 표현하여 위상정렬을 할 때 각 순서를 이어주는것 만으로는 불충분하다.

5 4 3 2 1

이런 순서가 있다고 할때

5->4

4->3

3->2

2->1

이렇게만 만들어주면 안된다.

위상정렬을 할 수 있도록

5->3

5->2

5->1

4->2

4->1

3->1

위의 간선도 만들어 주어 진입차수표가 아래처럼 만들어지도록 간선을 추가해야된다.

team            5 4 3 2 1

indegree      0 1 2 3 4

이렇게 만들어주면 이제 변한 순위의 간선들을 스왑해주면 된다.

2

2 4

3 4

라면

4->2

4->3

으로 바꾸어주고 진입차수표를 갱신시켜준다.

이전 진입차수표에서 2,3의 진입차수를 1씩 줄여주고 4의 진입차수를 2늘려주면된다.

변경된 순위에 따라 갱신된 간선과 진입차수표를 토대로 위상정렬을 실행한다.

이때 큐에 넣는과정에서 큐 안에 2개이상의 팀이 들어온다면 순위가 정확하지 않은것

이다.순위를 정하기 위해서는 차례대로 하나씩 들어와야 한다.

일관성이 깨지는 경우는 사이클이 있는 경우이다.

문제에서 순위가 바뀐 모든팀의 목록을 준다고 하였기 때문에 틀린순 있어도 순위가 

정해지지 않는경우는 없다.처음에 모든 팀의 목록이 주어지지 않는경우를 생각하여 ?

출력을 처리해서 틀렸다.

문제에서 ?가 출력되는 입력은 주어질수 없다.

import sys
from collections import deque
 
T=int(sys.stdin.readline())
for _ in range(T):
    n=int(sys.stdin.readline())#팀의 수
    ranking=list(map(int,sys.stdin.readline().split()))
    tree=[[] for _ in range(n+1)]#랭킹트리
    inDegree=[0 for _ in range(n+1)]#진입차수
    q=deque()
    for i in range(0,n-1):#순위를 토대로 트리생성
        for j in range(i+1,n):
            tree[ranking[i]].append(ranking[j])
            inDegree[ranking[j]]+=1
 
 
    m=int(sys.stdin.readline())#바뀐 순위 개수
    for _ in range(m):
        change_a,change_b=map(int,sys.stdin.readline().split())
        check=True
        for i in tree[change_a]:
            if i==change_b:#change_a가 더 높은 순위 의 팀일때
                tree[change_a].remove(change_b)
                tree[change_b].append(change_a)
                inDegree[change_b]-=1
                inDegree[change_a]+=1
                check=False
        if check:#change_b가 더 높은 순위 의 팀일때
            tree[change_b].remove(change_a)
            tree[change_a].append(change_b)
            inDegree[change_a] -= 1
            inDegree[change_b] += 1
 
 
    for i in range(1,n+1):#진입차수 0인거 찾기
        if inDegree[i]==0:
            q.append(i)
 
    result=0  #0가능 1불가
    result_list=[]
    if not q:#진입차수가 처음부터 0이 없을때
        result=1
    while q:
        if len(q)>1:#두개이상 들어왔을때
            result=1
            break
        a=q.popleft()
        result_list.append(a)
        for i in tree[a]:
            inDegree[i]-=1
            if inDegree[i]==0:
                q.append(i)
            elif inDegree[i]<0:#사이클이 있을때
                result=1
                break
 
    if result>0 or len(result_list)<n:
        print('IMPOSSIBLE')
    else:
        print(*result_list)