악곱 == 악성곱슬

그래프 이론, 신장 트리

---

해당 문제는 그래프 이론에 대한 문제이다. 신장 트리의 특징을 알고 있는가 물어보는 문제이다. 신장 트리의 간선의 개수는 노드 개수 - 1 이다.

해당 문제를 보자마자 최소 신장 트리를 구하기 위해 기계적으로 Union-find 코드를 작성하고 보니, 단순히 개수만 출력하는 문제였다. 따라서 다 지우고 입력받은 노드의 개수 - 1을 출력하였더니 정답… 항상 개념을 인지하고 사고하는 습관을 길러야 겠다.

코드는 아래와 같다.

import sys

# def find_parent(parent, x):
#     if parent[x] != x:
#         parent[x] = find_parent(parent, parent[x])
#     return parent[x]
#
#
# def union_parent(parent, a, b):
#     a = find_parent(parent, a)
#     b = find_parent(parent, b)
#     if a < b:
#         parent[b] = a
#     else:
#         parent[a] = b

def solution():
    n, m = map(int, sys.stdin.readline().rstrip().split())
    parent = [0] * (n + 1)
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        # union_parent(parent, a, b)
    # kinds = set(parent)
    # return len(kinds)
    return n - 1

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        print(solution())