[BOJ/C++] 24542 튜터-튜티 관계의 수 : DFS

문제

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

풀이

문제에서 주어진 것은 사이클이 없는 형태의 양방향 그래프
➡️모든 노드가 이어져있다는 보장이 없음
➡️여러 개의 트리 집합체라고 해석 가능

하나의 트리에 대해 최초로 교육 자료르 받는 인원이 최소가 되는 방법의 수 🟰 트리의 노드 수

문제는 여러 개의 트리로 이루어져 있으므로 총 경우의 수는 트리의 노드 수를 모두 곱한 값

ex) 3 * 3 = 9

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[200001];
bool visited[200001];

long long dfs(int x) {
	long long cnt = 1;
	visited[x] = true;

	for (int i = 0; i < v[x].size(); i++) {
		int next = v[x][i];

		if (!visited[next]) {
			cnt += dfs(next);
		}
	}

	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	long long ans = 1;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		if (visited[i])	continue;
		ans = (ans * dfs(i)) % 1000000007;
	}

	cout << ans;

	return 0;
}