문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 즉, 트리는 정점 개수가 n개, 간선 개수가 n-1개인 그래프이다.

그래프가 주어졌을 때, 트리의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n과 m이 주어진다. (1 ≤ n ≤ 500, 0 ≤ m ≤ n(n-1)/2) n은 정점의 개수, m은 간선의 개수이다. 다음 m개의 줄에는 간선을 나타내는 두 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스마다 “Case x:“를 출력한다. (x는 테스트 케이스 번호이고 1부터 시작한다.)

트리의 개수 t가 0이면 “No trees.”를, t가 1이면 “There is one tree.”를, t > 1이면 “A forest of t trees.”를 출력한다.

풀이

이 문제는 주어진 그래프에서 트리가 몇 개 있는지 세는 문제이다. 트리의 조건은 다음과 같다:

1. 연결되어 있다 (하나의 연결 요소)
2. 사이클이 없다
3. 정점이 n개일 때 간선이 n-1개

접근 방법

각 연결 요소를 찾고, 그 연결 요소가 트리인지 확인한다. 트리 판별 방법:

1. DFS를 수행하며 사이클이 있는지 확인
2. 간선의 개수가 정점의 개수 - 1인지 확인

사이클 판별

DFS를 수행하면서:

• 이미 방문한 노드를 다시 방문하면 (단, 바로 직전 노드 제외) → 사이클 존재
• 모든 노드를 방문했을 때 사이클이 없으면 → 트리 가능성 있음

트리 조건 확인

사이클이 없더라도 간선 수가 정점 수 - 1이어야 트리이다.

코드

def main():
    case_num = 1

    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

        edges = []
        for _ in range(m):
            u, v = map(int, input().split())
            edges.append((u, v))

        graph = [[] for _ in range(n + 1)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * (n + 1)
        tree_count = 0

        def dfs(cur, prev, nodes, edges):
            visited[cur] = True
            nodes.add(cur)
            for neighbor in graph[cur]:
                # 부모 방문 방지
                if neighbor == prev:
                    continue
                # 사이클 발견하면 빠져나오기
                if visited[neighbor]:
                    return False
                edges.add(tuple(sorted((cur, neighbor))))
                if not dfs(neighbor, cur, nodes, edges):
                    return False
            return True

        for i in range(1, n + 1):
            if not visited[i]:
                nodes = set()
                edges = set()

                # 사이클 확인
                if not dfs(i, 0, nodes, edges):
                    continue

                # 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
                if len(edges) == len(nodes) - 1:
                    tree_count += 1

        if tree_count == 0:
            print(f"Case {case_num}: No trees.")
        elif tree_count == 1:
            print(f"Case {case_num}: There is one tree.")
        else:
            print(f"Case {case_num}: A forest of {tree_count} trees.")

        case_num += 1


if __name__ == "__main__":
    main()

코드 설명

그래프 구성

graph = [[] for _ in range(n + 1)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

• 인접 리스트로 양방향 그래프 구성

DFS 함수

def dfs(cur, prev, nodes, edges):
    visited[cur] = True
    nodes.add(cur)
    for neighbor in graph[cur]:
        # 부모 방문 방지
        if neighbor == prev:
            continue
        # 사이클 발견하면 빠져나오기
        if visited[neighbor]:
            return False
        edges.add(tuple(sorted((cur, neighbor))))
        if not dfs(neighbor, cur, nodes, edges):
            return False
    return True

• cur: 현재 노드
• prev: 직전에 방문한 노드 (부모 노드)
• nodes: 현재 연결 요소의 정점 집합
• edges: 현재 연결 요소의 간선 집합

사이클 판별 로직:

• neighbor == prev: 바로 직전 노드는 무시 (양방향 간선)
• visited[neighbor]: 이미 방문한 노드를 다시 만나면 사이클
• 사이클이 발견되면 False 반환

트리 개수 세기

for i in range(1, n + 1):
    if not visited[i]:
        nodes = set()
        edges = set()

        # 사이클 확인
        if not dfs(i, 0, nodes, edges):
            continue

        # 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
        if len(edges) == len(nodes) - 1:
            tree_count += 1

• 방문하지 않은 각 연결 요소에 대해 DFS 수행
• 사이클이 없고 간선 수 = 정점 수 - 1이면 트리로 카운트

출력 형식

if tree_count == 0:
    print(f"Case {case_num}: No trees.")
elif tree_count == 1:
    print(f"Case {case_num}: There is one tree.")
else:
    print(f"Case {case_num}: A forest of {tree_count} trees.")

• 트리 개수에 따라 다른 형식으로 출력

시간 복잡도

• 각 테스트 케이스마다:
  • 그래프 구성: O(m)
  • DFS 탐색: O(n + m)
  • 전체: O(n + m)

n ≤ 500, m ≤ n(n-1)/2이므로 충분히 빠르게 해결할 수 있다.

트리의 성질

트리는 다음 조건 중 하나를 만족한다:

1. n개의 정점과 n-1개의 간선을 가지며 사이클이 없다
2. 임의의 두 정점 사이에 경로가 정확히 하나 존재한다
3. 간선을 하나 제거하면 두 개의 연결 요소로 분리된다
4. 사이클이 없지만 간선을 하나 추가하면 사이클이 생긴다

이 문제에서는 1번 조건을 사용하여 트리를 판별한다.

주의 사항

1. 양방향 간선: DFS에서 직전 노드로 돌아가는 것은 사이클이 아니다.
2. 간선 중복 방지: 간선을 set에 저장할 때 정렬하여 (u, v)와 (v, u)를 같은 간선으로 처리한다.
3. 연결 요소 분리: 각 연결 요소를 독립적으로 판별해야 한다.
4. 출력 형식: 트리 개수에 따라 정확한 문구를 출력해야 한다.

다른 접근 방법

Union-Find를 사용하여 더 효율적으로 해결할 수도 있다. Union 연산 중 이미 같은 집합에 속한 노드를 연결하려 하면 사이클이 생긴다는 점을 이용한다.