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

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

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

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;

int N;

//양방향 그래프
vector<vector<int>> adj(200000, vector<int>());

vector<int> visited;

//순회한 정점의 개수 반환
int bfs(int start) {
	int size = 0;

	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (visited[cur]) continue;
		visited[cur] = 1;

		size++;

		for (int i = 0; i < adj[cur].size(); ++i) {
			int next = adj[cur][i];
			if (visited[next]) continue;
			q.push(next);
		}

	}

	return size;
}

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

	int M;
	cin >> N >> M;

	for (int i = 0; i < M; ++i) {
		int x, y;
		cin >> x >> y;

		x--; y--;

		adj[x].push_back(y);
		adj[y].push_back(x);
	}


	long long res = 1;
	visited.clear();
	visited = vector<int>(N, 0);
	for (int i = 0; i < N; ++i) {
		if (!visited[i]) {
			res *= (long long)bfs(i);
			res %= 1000000007;
		}
	}
	cout << res;
	return 0;
}