Round Dance

Análisis oficial 

Explicación

Las condiciones se pueden representar como un grafo. Si la persona en $1$ recuerda a $2$, entonces $1$ debe estar junto a $2$. Si $2$ recuerda a $3$, entonces $2$ debe estar junto a $3$. Esto crea una componente conexa $1-2-3$.

La primera observación es que el número máximo de danzas circulares es el número de componentes conexas. Si dos nodos deben estar uno junto al otro, entonces estarán en una misma componente conexa. Separar estos dos nodos no cumpliría las condiciones dadas.

La segunda observación es que se pueden fusionar cualesquiera dos danzas circulares si y solo si un nodo tiene un solo vecino, lo que significa que las danzas circulares no forman un ciclo.

Una danza circular cíclica no se puede fusionar con otra danza circular porque cada nodo puede tener a lo sumo dos vecinos. Como una danza circular ya cíclica da a cada nodo sus dos vecinos, conectar las dos danzas crearía una contradicción.

Finalmente, todas las componentes conexas no cíclicas se pueden fusionar en una sola componente conexa. Fusionar dos componentes conexas no cíclicas crea otra componente conexa no cíclica. Así, podemos fusionar todas las componentes conexas no cíclicas entre sí en una componente conexa no cíclica.

Implementación

Complejidad temporal: $\mathcal{O}(n)$

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
	int n;
	cin >> n;
 
	vector<set<int>> adj(n);
 
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
 
		a--;
 
		// evitar duplicados
		adj[i].insert(a);
		adj[a].insert(i);
	}
 
	int min_num = 0, max_num = 0;
	int mergeable = 0;
 
	vector<bool> visited(n);
 
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			max_num++;
 
			queue<int> q;
			q.push(i);
			visited[i] = true;
 
			vector<int> component = {i};
 
			while (!q.empty()) {
				int curr = q.front();
				q.pop();
 
				for (int e : adj[curr]) {
					if (!visited[e]) {
						visited[e] = true;
						q.push(e);
						component.push_back(e);
					}
				}
			}
 
			for (int e : component) {
				if (adj[e].size() == 1) {  // solo un vecino
					mergeable++;
					break;
				}
			}
		}
	}
 
	min_num = max_num - max(0, mergeable - 1);
 
	cout << min_num << " " << max_num << "\n";
}
 
int main() {
	int t;
	cin >> t;
 
	while (t--) { solve(); }
}