greentea31's Note

https://www.acmicpc.net/problem/24542

풀이 과정

친분 관계 사이를 기반으로 튜터-튜티 지정이 가능하며, 교육 자료는 튜터 -> 튜티 방향으로 전달할 수 있다. 교육생간의 친분 관계가 포레스트인 그래프로 주어질 때 모든 교육생에게 자료가 전달되기 위해 찬솔이가 전해줘야 하는 인원수의 최소가 될 때의 튜터-튜티 관계를 정하는 경우의 수를 구하는 문제이다.

각 연결요소에 속해있는 정점의 개수를 정답 변수에 곱하는 방법으로 답을 구할 수 있다. 1 - 2 - 3, 4 - 5 - 6 - 7 - 8 이렇게 연결되어 있을 때의 경우는 3x5 = 15개의 경우의 수가 나올 것이다.

소스 코드

import sys
import collections


def bfs(x, visit, graph):
    q = collections.deque([x])
    visit[x] = True
    number = 1

    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if visit[nxt]:
                continue
            q.append(nxt)
            visit[nxt] = True
            number += 1

    return number


graph = collections.defaultdict(list)
N, M = map(int, sys.stdin.readline().split())
visit = [False for _ in range(N+1)]
answer = 1
mod = 1000000007

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for v in range(1, N+1):
    if not visit[v]:
        answer *= bfs(v, visit, graph)
        answer %= mod

print(answer)