BOJ [G4 | 12082] Bad Horse (Small1) (python)

As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn't about to spend his valuable time figuring out how to split the League members by himself. That what he's got you -- his loyal henchman -- for.

문제 설명

모든 멤버를 두개의 팀으로 나누는 문제이다.
입력으로는 각 멤버 짝의 입력이 주어지는데, 해당 멤버는 서로 같은 팀에 두면 안된다.

풀이

이분 그래프를 이용해 풀었다.

import sys
input = sys.stdin.readline


def check(graph):
    color = {}
    
    for v in graph.keys(): 
        color[v] = 0
    
    for v in graph.keys():
        if color[v]:
            continue
        
        s = [v]
        while s:
            e = s.pop()
            c = 2 if color[e] == 1 else 1
            if not color[e]:
                color[e] = c
            for u in graph[e]:
                # 색칠이 안되어있으면 색칠
                if not color[u]:
                    color[u] = -color[e]
                    s.append(u)
                # 같은 색이면 False
                elif color[u] == color[e]:
                    return False
    return True

def solve():
    nPair = input().strip()
    graph = {}
    for _ in range(int(nPair)):
        a,b = input().split()
        if not a in graph:
            graph[a] = []
            graph[a].append(b)
        else:
            graph[a].append(b)
    
        if not b in graph:
            graph[b] = []
            graph[b].append(a)
        else:
            graph[b].append(a)
            

    return check(graph)

for i in range(int(input())):
    if solve():
        print(f"Case #{i+1}: Yes")
    else:
        print(f"Case #{i+1}: No")
        ```

깜빡하고 Case에서 +1을 안해줘서 첫 시도는 틀렸다..