백준 9466번: 텀 프로젝트

[문제 링크]

9466번: 텀 프로젝트

---

그래프의 오일러 서킷과 관련된 문제였다. 순환을 이루는 정점들은 서로 팀을 이루고 있다고 볼 수 있고, 순환하지 않는 정점들의 개수를 찾아주면 된다.

---

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

int n;
int adj[100001];
bool visited[100001];

int dfs(int here, vector<int>& circuit) {

	visited[here] = true;
	circuit.push_back(here);

	int there = adj[here];
	if (!visited[there]) {
		return dfs(there, circuit);
	}
	return there;
}

int bfs(int start, vector<int>& circuit) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		circuit.push_back(here);

		int there = adj[here];

		if (!visited[there]) {
			visited[there] = true;
			q.push(there);
		}
		else
			return there;
	}
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--) {
		memset(visited, false, sizeof(visited));
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> adj[i];

		int result = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				vector<int> circuit;
				int idx = bfs(i, circuit);
				int len = circuit.size();

				for (int i = 0; i < len; i++) {
					if (idx == circuit[i]) break;
					result++;
				}
			}
		}
		cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 168 day