백준 11724

이 문제의 경우 기초적인 BFS문제 이다 일단 이문제가 원하는 건 경로가 아닌 루트의 갯수를 원하는 것이다. 이에 나는 평균적인 성능을 보장해 주는 BFS를 사용하였다.

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

vector<int> bfsV[1001];
queue<int> bfsQ;
int arr[1001] = { 0, };
int N, M;
int cnt = 0;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		bfsV[temp1].push_back(temp2);
		bfsV[temp2].push_back(temp1);
	}
	for (int i = 1; i <= N; i++) {
		if (arr[i] == 0) {
			bfsQ.push(i);
			arr[i] = cnt;
			cnt++;
			while (!bfsQ.empty()) {
				int temp3;
				temp3 = bfsQ.front();
				bfsQ.pop();
				for (int j = 0; j < bfsV[temp3].size(); j++) {
					if (arr[bfsV[temp3][j]] == 0) {
						bfsQ.push(bfsV[temp3][j]);
						arr[bfsV[temp3][j]] = cnt;
					}
				}
			}
		}
	}
	cout << cnt;
}