[C++]백준 24542번 튜터-튜티 관계의 수

📌문제 링크

---

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

📌문제 설명

---

포레스트이기때문에 같은 친분 관계안이면 어떤 사람에게 교육 자료를 나누어줘도 가능하다. 따라서 문제를 치환하면 그룹별 그룹인원수를 모두 곱해주면 된다.

📌코드

---

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
vector<pair<int, int>> edges;
int parent[200001], sizel[200001];
int N, M;
long long result = 1;

void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({a, b});
    }
}

void init() {
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        sizel[i] = 1;
    }
}

int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

void unite(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a != b) {
        if (sizel[a] < sizel[b]) swap(a, b);
        parent[b] = a;
        sizel[a] += sizel[b];
    }
}

void solve() {
    input();
    init();
    for (auto& edge : edges) {
        int a = edge.first;
        int b = edge.second;
        if (findParent(a) != findParent(b)) {
            unite(a, b);
        }
    }

    vector<int> roots;
    for(int i = 1; i <= N; i++){
        if(parent[i] == i){
            roots.push_back(i);
        }
    }
    for(auto it : roots){
        result = (result * sizel[it]) % MOD;
    }
    cout << result << '\n';
}

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