[BOJ] 24542 튜터-튜티 관계의 수

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

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

---

문제

퓨처테크아케데미(주)는 올해로 4년째 엘리트 알고리즘 SW교육-「헬로알고」라는 브랜드로 국내는 물론 해외 14개국 청소년들을 대상으로 SW교육을 실시하고 있는 교육회사입니다. 또한 중소벤처기업부와 한국교육학술정보원이 선정한 '2021비대면스타트업 교육회사', 동국대학교 'SW코딩역량강화캠프 교육회사' 선정 등 늘 새로운 것에 도전하는 젊은 열정의 에듀테크 회사이기도 합니다. 2022 국내외 온·오프라인 사업의 새로운 도전을 위해 SW교육 지도 및 컨텐츠 연구개발 분야에 함께할 젊고 패기있는 SW인재를 찾습니다!

대학생 찬솔이는 이번 학기부터 헬로알고에서 멘토로 활동하게 되었다. 현재 찬솔이가 담당한 반에는 총 N$N$명의 교육생이 있다.

사전 정보를 통해 찬솔이는 헬로알고 교육생 간의 친분 관계를 나타내는 양방향 그래프를 하나 획득할 수 있었다. 정말 특이하게도 이 친분 관계를 나타낸 그래프는 포레스트 형태였다. 포레스트란 사이클이 없는 그래프를 의미한다.

찬솔이는 이 교육생 간 친분관계를 토대로 교육생들끼리 튜터-튜티 관계를 구성하고자 한다. 튜터-튜티 관계는 기존에 친분 관계가 있던 두 사람 사이에서만 정할 수 있으며 단방향으로만 지정할 수 있다.

찬솔이가 배포한 교육 자료는 튜터가 튜티에게만 전달할 수 있도록 하였다. 이런 방식으로 모든 교육생에게 교육 자료가 전달되어야만 한다. 이렇게 되면 부득이하게 찬솔이로부터 최초로 교육 자료를 받는 인원이 생길 수밖에 없다. 찬솔이는 수줍음이 많은 성격이기 때문에 이런 인원수가 최소가 되기를 희망한다.

위 조건을 만족하면서 교육생의 튜터-튜티 관계를 정하는 경우의 수를 1000000007로 나눈 나머지를 출력하자.

---

입력

교육생의 수 N과 친분 관계의 수 M이 공백으로 구분되어 주어진다. (2≤N≤200000, 1≤M≤N−1)

다음 M개의 줄에 친분 관계를 맺고 있는 두 교육생인 u, v가 공백으로 구분되어 주어진다. (1≤u,v≤N, u≠v)

교육생의 번호는 1 이상 N 이하의 정수이며, 주어지는 그래프는 포레스트이다.

---

출력

첫째 줄에 튜터-튜티 관계를 정하는 경우의 수를 1000000007로 나눈 나머지를 출력한다.

---

풀이

잘 생각해 보면 결국 주어진 그래프들의 크기를 곱하는 문제이다.

1. 방문하지 않은 정점이라면 해당 정점이 포함된 그래프의 크기를 구한다.
2. 답에 구한 그래프의 크기를 곱한다.
3. 방문하지 않은 정점이 없을 때까지 1,2번을 반복한다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long
#define mod 1000000007;

using namespace std;

int N,M;
vector<int> v[200001];
bool check[200001];

ll bfs(int i){ // 트리의 크기를 구하는 넓이 우선 탐색
    ll cnt=0;
    queue<int> q;
    q.push(i);
    check[i]=true;
    
    while(!q.empty()){
        int s=q.front(); q.pop();
        cnt++;
        for(int i=0;i<v[s].size();i++){
            int e=v[s][i];
            if(!check[e]){
                check[e]=true;
                q.push(e);
            }
        }
    }
    return cnt;
}

void input() {
    cin>>N>>M;
    int start,end;
    for(int i=0;i<M;i++){
        cin>>start>>end;
        v[start].push_back(end);
        v[end].push_back(start);
    }
}

void init() {
}


void solution() {
    ll ans=0;
    for(int i=1;i<=N;i++){
        if(!check[i]){
            if(ans==0) ans=bfs(i);
            else{
                ans*=bfs(i);
                ans%=mod;
            }
        }
    }
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}