[백준/24542/파이썬] 튜터-튜티 관계의 수

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

24542번: 튜터-튜티 관계의 수

Problem

• 대학생 찬솔이는 이번 학기부터 헬로알고에서 멘토로 활동하게 되었다. 현재 찬솔이가 담당한 반에는 총 명의 교육생이 있다.
• 찬솔이는 이 교육생 간 친분관계를 토대로 교육생들끼리 튜터-튜티 관계를 구성하고자 한다. 튜터-튜티 관계는 기존에 친분 관계가 있던 두 사람 사이에서만 정할 수 있으며 단방향으로만 지정할 수 있다.
• 조건을 만족하면서 교육생의 튜터-튜티 관계를 정하는 경우의 수를 1000000007로 나눈 나머지를 출력하자.

조건

• 사전 정보를 통해 찬솔이는 헬로알고 교육생 간의 친분 관계를 나타내는 양방향 그래프를 하나 획득할 수 있었다. 정말 특이하게도 이 친분 관계를 나타낸 그래프는 포레스트 형태였다. 포레스트란 사이클이 없는 그래프를 의미한다.
• 찬솔이가 배포한 교육 자료는 튜터가 튜티에게만 전달할 수 있도록 하였다. 이런 방식으로 모든 교육생에게 교육 자료가 전달되어야만 한다. 이렇게 되면 부득이하게 찬솔이로부터 최초로 교육 자료를 받는 인원이 생길 수밖에 없다. 찬솔이는 수줍음이 많은 성격이기 때문에 이런 인원수가 최소가 되기를 희망한다.
• 교육생의 수 N과 친분 관계의 수 M이 공백으로 구분되어 주어진다. (2≤N≤200000, 1≤M≤N−1)
• 다음 M개의 줄에 친분 관계를 맺고 있는 두 교육생인 u, v가 공백으로 구분되어 주어진다. (1≤u,v≤N)
• 교육생의 번호는 1 이상 N 이하의 정수이며, 주어지는 그래프는 포레스트이다.

SOL

Union-Find를 이용해서, 하나마다의 유니온 크기를 구해서,  경우의 수를 다 곱해주는 걸로 풀었다!

#Union Find
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,M=map(int,input().split())
parent = [x for x in range(N+1)]

def find(target):
    if target==parent[target]:
        return target
    parent[target] = find(parent[target])
    return parent[target]

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

for i in range(M):
    a,b=map(int,input().split())
    if find(a) != find(b):
        union(a,b)

ans={}
for i in range(1,N+1):
    a=find(i)
    if ans.get(a)==None:
        ans[a] =1
    else:
        ans[a]+=1

total=1
for b in ans.values():
    total =(total%1000000007*b%1000000007)%1000000007
print(total)