Encuentre elementos que cambien de grupo o que nunca se muevan con otro elemento del grupo

Dadas dos instantáneas S1 y S2 de N elementos, la tarea es encontrar los elementos que están cambiando sus grupos y los que nunca formaron grupos con otros elementos del grupo (aunque pueden dividirse y formar un subgrupo separado).

Nota: La posición de un grupo y los elementos dentro de un grupo pueden cambiar. Los grupos pueden dividirse en subgrupos.

Ejemplos:

Entrada: S1: {{1, 2, 3, 4}, {5, 6}, {7, 8}}, S2: {{1, 2}, {3}, {4, 5}, {7, 8}, {6}}
Salida: {1 2 3 6 7 8}, {1 2 3 4 5 6}
Explicación: Elementos en grupos [1, 2], [3], [6], [7, 8] nunca he estado 
con un elemento de otro grupo por lo que la respuesta es [1, 2, 3, 6, 7, 8].
Los elementos del grupo [7, 8] no han cambiado de grupo. 
De lo contrario, todos los demás elementos han roto o intercambiado el grupo.

Entrada: S1: {{1, 3, 8}, {2, 5}, {4}, {9, 6}, {7, 10, 11, 12}}, S2: {{1, 3}, { 9}, {8}, {12, 11}, {7, 6}, {2, 5}, {4, 10}}
Salida: {1 3 9 8 11 12 2 5}, {1 3 9 8 12 11 7 6 4 10}
Explicación: Los elementos de los grupos [1, 3], [9], [8], [11, 12], [2, 5] no han estado 
con un elemento de otro grupo, por lo que la respuesta es [1 , 3, 9, 8, 11, 12, 2, 5]. 
Solo [2, 5] no han cambiado de grupo. 
Todos los demás elementos han roto o intercambiado el grupo.

Enfoque ingenuo: El enfoque básico para resolver el problema como se menciona a continuación:

• Recorra cada grupo en la instantánea-1 (grupo-1).
• Recorre cada elemento del grupo 1.
• Encuentre el grupo del elemento en la instantánea-2 (grupo-2).
• Comprueba si group2 es un subconjunto de group1 o si ambos tienen los mismos elementos.

Complejidad temporal: O(N * (N + k) * k ² ) donde N es el número total de elementos y K es el elemento máximo en un grupo
Espacio auxiliar: O(1)

Enfoque eficiente: para resolver el problema de manera eficiente, siga cuidadosamente la siguiente idea:

• Para encontrar a las personas que cambiaron de grupo: Es fácil encontrar a las personas que no cambiaron de grupo: si el grupo de elementos es el mismo en ambas instantáneas. Todos los demás elementos han cambiado el grupo.
• Para encontrar a las personas que nunca han interactuado fuera de sus grupos: si el grupo final es un subconjunto o igual al grupo inicial, entonces sus elementos nunca han interactuado fuera de su grupo.
• Dado que ambos problemas comparan los grupos en instantáneas, podemos seguir el mismo enfoque, la única diferencia es cómo comparamos los grupos .

Siga los pasos para resolver el problema:

• Recorra cada grupo en la instantánea-2 (grupo-2).
• Para cualquier persona en el grupo-2.
• Busque el grupo de la persona en la instantánea-1 (grupo-1).
• Compruebe si group2 es un subconjunto de group1 o ambos, con las mismas personas.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print vector elements
void printVector(vector<int> vec)
{
    for (auto value : vec) {
        cout << value << " ";
    }
    cout << "\n";
}
 
// Function to check if one is subset of other
// or they are equal
bool isSubsetOrEqual(vector<int> parent,
                     vector<int> child,
                     bool strictEqual)
{
    // Check for size equality
    if (strictEqual ? child.size() != parent.size()
                    : child.size() > parent.size()) {
        return false;
    }
 
    // Initializing a hash set
    set<int> hashset;
    for (auto item : parent) {
        hashset.insert(item);
    }
 
    for (auto item : child) {
        if (hashset.find(item)
            == hashset.end())
            return false;
    }
    return true;
}
 
// Function to append vector
void appendVector(vector<int>& result,
                  vector<int> values)
{
    for (auto value : values) {
        result.push_back(value);
    }
}
 
// Function to assign the groups of elements
unordered_map<int, int>
getPersonToGroupIdxMap(vector<vector<int> > groups)
{
    unordered_map<int, int> personToGroupIdxMap;
    for (int groupIdx = 0; groupIdx < groups.size();
         groupIdx++) {
        for (auto person : groups[groupIdx]) {
            personToGroupIdxMap[person] = groupIdx;
        }
    }
    return personToGroupIdxMap;
}
 
// Function to find if interaction outside group
vector<int>
peoplesInteractionCheck(vector<vector<int> > initialGroups,
                        vector<vector<int> > finalGroups,
                        bool strictEqual)
{
    vector<int> result;
    unordered_map<int, int> initialPersonToGroupIdxMap
        = getPersonToGroupIdxMap(initialGroups);
 
    for (auto groupInFinal : finalGroups) {
        int person = groupInFinal[0];
 
        int initialGroupIdx
            = initialPersonToGroupIdxMap[person];
        vector<int> groupInInitial
            = initialGroups[initialGroupIdx];
 
        bool isSubsetOrEqualResult = isSubsetOrEqual(
            groupInInitial, groupInFinal, strictEqual);
 
        // For equal case, add in result
        // if groups are not equal.
        if (strictEqual && !isSubsetOrEqualResult) {
            appendVector(result, groupInFinal);
        }
 
        // For subset case, add in result
        // if groups are subset or equal.
        if (!strictEqual && isSubsetOrEqualResult) {
            appendVector(result, groupInFinal);
        }
    }
 
    return result;
}
 
// Driver code
int main()
{
    vector<vector<int> > initialGroups{ { 1, 3, 8 },
                                        { 2, 5 },
                                        { 4 },
                                        { 9, 6 },
                                        { 7, 10, 11, 12 } };
    vector<vector<int> > finalGroups{ { 1, 3 }, { 9 }, { 8 }, { 12, 11 }, { 7, 6 }, { 2, 5 }, { 4, 10 } };
 
    vector<int> peopleWithNoOutsideInteractions
        = peoplesInteractionCheck(initialGroups,
                                  finalGroups, false);
    cout << "Elements with no outside interactions\n";
    printVector(peopleWithNoOutsideInteractions);
 
    vector<int> peopleWhoSwitchedGroups
        = peoplesInteractionCheck(initialGroups,
                                  finalGroups, true);
    cout << "Elements that changed their groups\n";
    printVector(peopleWhoSwitchedGroups);
    return 0;
}

// JavaScript code for the above approach:
 
 
// Function to print vector elements
function printVector(vec)
{
    for (var value of vec) {
        process.stdout.write(value + " ");
    }
    process.stdout.write("\n");
}
 
// Function to check if one is subset of other
// or they are equal
function isSubsetOrEqual(parent, child, strictEqual)
{
    // Check for size equality
    if (strictEqual ? child.length != parent.length
                    : child.length > parent.length) {
        return false;
    }
 
    // Initializing a hash set
    let hashset = new Set();
    for (var item of parent) {
        hashset.add(item);
    }
 
    for (var item of child) {
        if (!hashset.has(item))
            return false;
    }
    return true;
}
 
// Function to append vector
function appendVector(result, values)
{
    result.push(...values)
}
 
// Function to assign the groups of elements
function getPersonToGroupIdxMap(groups)
{
    let personToGroupIdxMap = {};
    for (var groupIdx = 0; groupIdx < groups.length;
         groupIdx++) {
        for (var person of groups[groupIdx]) {
            personToGroupIdxMap[person] = groupIdx;
        }
    }
    return personToGroupIdxMap;
}
 
// Function to find if interaction outside group
function peoplesInteractionCheck(initialGroups, finalGroups,  strictEqual)
{
    let result = [];
    let initialPersonToGroupIdxMap
        = getPersonToGroupIdxMap(initialGroups);
 
    for (var groupInFinal of finalGroups) {
        let person = groupInFinal[0];
 
        let initialGroupIdx
            = initialPersonToGroupIdxMap[person];
        let groupInInitial
            = initialGroups[initialGroupIdx];
 
        let isSubsetOrEqualResult = isSubsetOrEqual(
            groupInInitial, groupInFinal, strictEqual);
 
        // For equal case, add in result
        // if groups are not equal.
        if (strictEqual && !isSubsetOrEqualResult) {
            appendVector(result, groupInFinal);
        }
 
        // For subset case, add in result
        // if groups are subset or equal.
        if (!strictEqual && isSubsetOrEqualResult) {
            appendVector(result, groupInFinal);
        }
    }
 
    return result;
}
 
// Driver code
let initialGroups = [ [ 1, 3, 8 ],
                                        [ 2, 5 ],
                                        [ 4 ],
                                        [ 9, 6 ],
                                        [ 7, 10, 11, 12 ] ];
let finalGroups = [[ 1, 3 ], [ 9 ], [ 8 ], [ 12, 11 ], [ 7, 6 ], [ 2, 5 ], [ 4, 10 ]];
 
let peopleWithNoOutsideInteractions
        = peoplesInteractionCheck(initialGroups,
                                  finalGroups, false);
console.log("Elements with no outside interactions");
    printVector(peopleWithNoOutsideInteractions);
 
let peopleWhoSwitchedGroups
        = peoplesInteractionCheck(initialGroups,
                                  finalGroups, true);
console.log("Elements that changed their groups");
printVector(peopleWhoSwitchedGroups);
 
 
// This code is contributed by phasing17

Elements with no outside interactions
1 3 9 8 12 11 2 5 
Elements that changed their groups
1 3 9 8 12 11 7 6 4 10 

Complejidad temporal: O(N * k)
Espacio auxiliar: O(N * k)