[못 푼 문제] 백준 1707번

이전에는 노드투 노드 그래프가 입력이 되면

graph = [[0] for i in range(n+1)]처럼 했다면 메모리를 줄이기 위해 새로운 방법을 도입한다.

for i in range(k):
	a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

와 같이 그래프를 만들자. 메모리 부분에서 훨씬 더 효율적이다. 그리고

시간초과.....가 나오면 무조건 sys.stdin.readline()을 생각하자

import sys
sys.setrecursionlimit(1000000)

def dfs(node, group):
    visited[node] = group
    for i in graph[node]:
        if not visited[i]:
            a = dfs(i, -group)
            if not a:
                return False
        else:
            if visited[i] == group:
                return False
    return True

for _ in range(int(input())):
    u, v = map(int, sys.stdin.readline().split())
    graph = [[] for i in range(u+1)]
    for _ in range(v):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    visited = [False] * (u+1)
    for i in range(1, u+1):
        if not visited[i]:
            result = dfs(i, 1)
            if not result:
                break
    print("YES" if result else "NO")