Encuentra el número de triángulos únicos entre N triángulos dados

Dadas tres arrays a[], b[] y c[] de N elementos que representan los tres lados de N triángulos. La tarea es encontrar el número de triángulos que son únicos de los triángulos dados. Un triángulo no es único si todos sus lados coinciden con todos los lados de algún otro triángulo en longitud.
Ejemplos: 
 

Entrada: a[] = {1, 2}, b[] = {2, 3}, c[] = {3, 5} 
Salida: 2 
Los triángulos tienen lados 1, 2, 3 y 2, 3, 5 respectivamente . 
Ninguno de ellos tiene los mismos lados. Por lo tanto, ambos son únicos.
Entrada: a[] = {7, 5, 8, 2, 2}, b[] = {6, 7, 2, 3, 4}, c[] = {5, 6, 9, 4, 3} 
Salida : 1 
Solo el triángulo con lados 8, 2 y 9 es único. 
 

Enfoque: La idea es, para cada triángulo, clasificar todos sus lados y luego almacenarlos en un mapa, si esos tres lados ya están presentes en el mapa, entonces aumente la frecuencia en 1, de lo contrario, su frecuencia será 1. El conteo de elementos del mapa que tienen frecuencia 1 al final será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of unique triangles
int UniqueTriangles(int a[], int b[], int c[], int n)
{
    vector<int> sides[n];
 
    // Map to store the frequency of triangles
    // with same sides
    map<vector<int>, int> m;
 
    for (int i = 0; i < n; i++) {
 
        // Push all the sides of the current triangle
        sides[i].push_back(a[i]);
        sides[i].push_back(b[i]);
        sides[i].push_back(c[i]);
 
        // Sort the three sides
        sort(sides[i].begin(), sides[i].end());
 
        // Store the frequency of the sides
        // of the triangle
        m[sides[i]] = m[sides[i]] + 1;
    }
 
    map<vector<int>, int>::iterator i;
 
    // To store the count of unique triangles
    int count = 0;
    for (i = m.begin(); i != m.end(); i++) {
 
        // If current triangle has unique sides
        if (i->second == 1)
            count++;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int a[] = { 7, 5, 8, 2, 2 };
    int b[] = { 6, 7, 2, 3, 4 };
    int c[] = { 5, 6, 9, 4, 3 };
 
    int n = sizeof(a) / sizeof(int);
 
    cout << UniqueTriangles(a, b, c, n);
 
    return 0;
}

# Python3 implementation of the approach
from collections import defaultdict
 
# Function to return the number
# of unique triangles
def UniqueTriangles(a, b, c, n):
 
    sides = [None for i in range(n)]
 
    # Map to store the frequency of
    # triangles with same sides
    m = defaultdict(lambda:0)
 
    for i in range(0, n):
 
        # Push all the sides of the current triangle
        sides[i] = (a[i], b[i], c[i])
 
        # Sort the three sides
        sides[i] = tuple(sorted(sides[i]))
 
        # Store the frequency of the sides
        # of the triangle
        m[sides[i]] += 1
 
    # To store the count of unique triangles
    count = 0
    for i in m:
 
        # If current triangle has unique sides
        if m[i] == 1:
            count += 1
 
    return count
 
# Driver code
if __name__ == "__main__":
 
    a = [7, 5, 8, 2, 2]
    b = [6, 7, 2, 3, 4]
    c = [5, 6, 9, 4, 3]
 
    n = len(a)
 
    print(UniqueTriangles(a, b, c, n))
     
# This code is contributed by Rituraj Jain

1

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)