Tag: disjoint set

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())
truth = list(map(int, input().split()))
truth_num = truth[0]
truth_people = set(truth[1:])

parent = list(range(N + 1))
parties = []

for _ in range(M):
    party = list(map(int, input().split()))
    party_people = party[1:]
    parties.append(party_people)
    
    # 같은 파티 사람들을 union
    for i in range(len(party_people) - 1):
        union(parent, party_people[i], party_people[i + 1])

# 진실을 아는 사람들과 같은 그룹인지 확인
result = 0
for party in parties:
    can_lie = True
    for person in party:
        for truth_person in truth_people:
            if find(parent, person) == find(parent, truth_person):
                can_lie = False
                break
        if not can_lie:
            break
    if can_lie:
        result += 1

print(result)

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.")