[python]1707번 이분 그래프

이분 그래프에 대한 개념을 알게 되었다.

정점들 간에 두 집합이 있다.

두 집합 간에는 간선으로 연결 될 수 있지만

집합 안에서는 간선이 존재해서는 안된다.

처음 내가 생각한 알고리즘은

굳이 그래프로 구현하지 않고 dictionary key에다가 정점들을 저장하고 

포함 유무로 문제를 풀려했다.

import sys
from collections import defaultdict
for _ in range(int(input())):
    fstl = defaultdict(list)
    scdl = defaultdict(list)
    edge,line = map(int,input().split())
    for i in range(line):
        fst,scd = map(int,input().split())
        if fst not in fstl and scd not in scdl and scd not in fstl and fst not in scdl:
            fstl[fst].append(1)
            scdl[scd].append(1)
        elif fst in fstl and scd not in scdl and fst not in scdl and scd not in fstl:
            fstl[fst].append(1)
            scdl[scd].append(1)
        elif fst in scdl and scd not in fstl and fst not in fstl and scd not in scdl:
            fstl[scd].append(1)
            scdl[fst].append(1)
        elif fst not in fstl and scd  in scdl and fst not in scdl and scd not in fstl:
            fstl[fst].append(1)
            scdl[scd].append(1)
        elif fst not in scdl and scd in fstl and fst not in fstl and scd not in scdl:
            fstl[scd].append(1)
            scdl[fst].append(1)
        else:
            print('NO')
            break
    else:
        print('YES')
        continue
    break

당연히도 오답이었다.

첫번째 원인은 일단 조건들이 정밀하지도 않았다.

두번째는 내가 임의로 정점들을 집합으로 분류했는데,

이것은 후에 간선 그래프가 내가 정한 집합에 따라 맞을 수도, 틀릴 수 도 있어 오답이다.

 

역시 정답은 그래프 순회로 판별하는 것이었다.

import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(123456)
def dfs(idx,clr):
    color[idx] = clr
    a = 1
    for next in stg[idx]:
        if color[next]==clr:    #다음 번 정점이 지금과 색깔이 같다면 이것은 잘못된것
            return 0
        if not color[next]:        #아직 방문한 적이 없다면
            a = dfs(next,2 if clr==1 else 1)   #다음 번 정점에는 지금과 다른 색깔로 저장
    return a
for _ in range(int(input().strip())):
    edge,line = map(int,input().split())
    stg = defaultdict(list)
    color = [0 for i in range(edge+1)]    #색깔 저장소
    for i in range(line):
        fst,scd = map(int,input().split())
        stg[fst].append(scd)
        stg[scd].append(fst)
    for i in stg:
        if not color[i]:    #방문한 적이 없다면
            rst = dfs(i,1)
            if not rst:     #이분 그래프가 아닐때
                break
    else:
        print("YES")
        continue
    print('NO')

나는  dfs로 풀어 통과하였다.

이때 시간초과 나기가 싫어 pypy3로 제출하였는데 되려 메모리 초과가 떠서 방황했다.