#include <bits/stdc++.h>

using namespace std;

class UndirectedGraph {
    // Grafo con estructura de lista de adjacencias, implementada como vector para mejorar la eficiencia de acceso/búsqueda
    map<string, vector<string>> users;
    int totalNodes = 0;


public:
    UndirectedGraph();
    void addUser(const string& userA, const string& userB);
    void find(const string& u);
    void clique(vector<string> R, vector<string> P, vector<string> X);
    void compact();
    void follow(int n);
    void showGraph();
};

/**
 * Constructor. No requiere parámetros. Dummy constructor.
 */
UndirectedGraph::UndirectedGraph() = default;

/**
 * Agrega un usuario nuevo al grafo. Hace una conexión bidireccional (al descomentar la línea comentada)
 * @param userA: String de usuario A conectado a usuario B
 * @param userB: String de usuario B conectado a usuario A
 */
void UndirectedGraph::addUser(const string& userA, const string& userB) {
    users[userA].push_back(userB);
    // users[userB].push_back(userA);
    totalNodes++;
}

/**
 * Muestra el grafo en pantalla. La representación es en forma de lista de adyacencia. Cada nodo está seguido de una
 * flecha con todas sus conexiones
 */
void UndirectedGraph::showGraph() {
    for (const auto& it: users){
        cout << it.first << "->";
        for (const auto& it2: it.second){
            cout << it2 << " ";
        }
        cout << endl;
    }
}

/**
 * Intenta encontrar si el usuario u existe en el grafo. Imprime en pantalla el resultado de la búsqueda. Comentado
 * está un código menos eficiente pero más sencillo, el cual aprovecha la forma en que se almacenó el grafo (map)
 * @param u: String de usuario a buscar en el grafo
 */
void UndirectedGraph::find(const string& u) {
    /*
    for (const auto& it: users){
        if (it.first == u){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
    */
    // Cola para guardar temporalmente los nodos
    queue<string> q;
    // Mapa para llevar nodos y un valor de verdad de si fueron visitados
    map<string, bool> visited;
    // Comienza, aleatoriamente, con el "primer" nodo del grafo
    q.push(users.begin()->first);
    visited[users.begin()->first] = true;
    // Itera hasta que la cola esté vacía
    while(!q.empty()) {
        // Remueve la cabeza de la cola
        string currentUser = q.front();
        // Revisa si el primer elemento de la cola es el buscado
        if (currentUser == u) {
            cout << "Yes" << endl;
            return;
        }
        // Retira el elemento
        q.pop();
        // Itera en el vector de currentUser
        for (auto &i : users[currentUser]) {
            // Si los nodos adyacentes a currentUser no han sido visitados, se agregan para ser visitados
            if (!visited[i]) {
                // Se revisa match
                if (i == u) {
                    cout << "Yes" << endl;
                    return;
                }
                // Se marca visitado
                visited[i] = true;
                q.push(i);
            }
        }
    }
    // No se retornó al visitar todos los nodos, implica que el elemento no se encontró
    cout << "No" << endl;
}

/**
 * Imprime en pantalla los usuarios con más cantidad de seguidores. El orden de impresión es arbitrario (dependiente
 * de cómo se agregaron) y no hay un criterio definido para conflictos (usuarios con igual cantidad de seguidores). Dada
 * la construcción del algoritmo, siempre se imprimirán los últimos en ser ingresados (los que estén más profundamente
 * en el grafo).
 * @param n: Cantidad de usuarios con más seguidores a buscar
 */
void UndirectedGraph::follow(int n) {
    // Si se piden más usuarios de los ingresados, retorna informando error
    if (totalNodes < n){
        cout << "Error: Cantidad de usuarios requeridos excede tamaño total de usuarios registrados" << endl;
        return;
    }
    // Vector de los usuarios más seguidos
    vector <string> mostFollowed;
    // String temporal para almacenar persona más seguida actual
    string currentMostFollowed;
    // Temporal para buscar el largo máximo
    int maxLength;
    // Crea una copia de usuarios, para así eliminar cuando se ha agregado uno
    map<string, vector<string>> copyOfUsers(users);
    // Itera n veces para los usuarios requeridos
     for (int i = 0; i < n; i++){
         // Reinicio para buscar nuevo largo máximo
         maxLength = 0;
         // Busca por todos los nodos del grafo el que tenga el mayor largo
         for (const auto& it: copyOfUsers){
             // Si se encontró uno con mayor largo, se actualiza el largo y se almacena parcialmente el nodo
             if (maxLength <= it.second.size()){
                 maxLength = it.second.size();
                 currentMostFollowed = it.first;
             }
         }
         // El máximo ha sido encontrado, se agrega al vector de más seguidos
         mostFollowed.push_back(currentMostFollowed);
         // Se elimina de la lista, para evitar repeticiones
         copyOfUsers.erase(currentMostFollowed);
     }
     // Impresión en pantalla
     for (const auto& it: mostFollowed){
         cout << it << endl;
     }
}

void UndirectedGraph::clique(vector<string> R, vector<string> P, vector<string> X) {
    // Revisa si están vacíos, lo que implicaría que hay un clique
    if (P.empty() && X.empty()){
        cout << "Clique found!" << endl;
        for (const auto& it: R)
            cout << it << " " << endl;
        return;
    }
    // Crea una copia de P para evitar problemas en el iterador
    vector<string> pCopy(P);
    for (const auto& v: pCopy){
        vector<string> unionSet;
        vector<string> intersectionSetPNv;
        vector<string> intersectionSetXNv;
        vector<string> neighborsP;
        vector<string> vVector = {v};
        // Obtiene los vecinos de P
        for (const auto& neighbors: users[v]) neighborsP.push_back(neighbors);
        // R u {v}
        set_union(R.begin(), R.end(), vVector.begin(), vVector.end(), back_inserter(unionSet));
        // Obtiene intersección P y N(v)
        set_intersection(P.begin(), P.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetPNv));
        set_intersection(X.begin(), X.end(), neighborsP.begin(), neighborsP.end(), back_inserter(intersectionSetXNv));
        clique(unionSet, intersectionSetPNv, intersectionSetXNv);
        vector<string> PminusV;
        vector<string> XunionV;
        // Obtiene P - {v} y X u {v}
        set_difference(P.begin(), P.end(), vVector.begin(), vVector.end(), inserter(PminusV, PminusV.begin()));
        set_union(X.begin(), X.end(), vVector.begin(), vVector.end(), back_inserter(XunionV));

        P = vector<string> (PminusV);
        X = vector<string> (XunionV);
    }


}

void UndirectedGraph::compact() {
    cout << "Compact" << endl;
}