La fraude téléphonique est un problème persistant. Pour la combattre, un suspect est identifié s'il effectue plus de K appels courts à des personnes différentes quotidiennement, avec au plus 20% de rappels. Un appel court est défini par une durée totale de 5 minutes ou moins. Lorsque deux suspects s'appellent mutuellement, ils sont potentiellement membres du même gang.

Spécificasions d'Entrée

Chaque cas de test est fourni dans un fichier d'entrée. La première ligne contient trois entiers positifs : K (≤500, seuil du nombre d'appels courts), N (≤10^3, nombre de numéros de téléphone distincts) et M (≤10^5, nombre d'enregistrements d'appels). Les M lignes suivantes décrivent les appels d'une journée au format :

appelant destinataire durée

où appelant et destinataire sont numérotés de 1 à N, et durée ne dépasse pas 1440 minutes par jour.

Spécifications de Sortie

Pour chaque gang détecté, affichez ses membres sur une ligne, triés par ordre croissant. Les gangs sont affichés selon l'ordre croissant de leur premier membre. Les numéros sont séparés par un seul espace, sans espaces superflus. Si aucun suspect n'est trouvé, affichez Aucun.

Exemple d'Entrée 1

5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1

Exemple de Sortie 1

3 5
6

Note : Dans cet exemple, l'individu 1 a 9 enregistrements avec 7 destinataires distincts. Parmi ceux-ci, 5 et 15 ont des conversations totales dépassant 5 minutes. Ainsi, 1 a effectué 5 appels courts, inférieurs au seuil de 5, et n'est donc pas un suspect.

Exemple d'Entrée 2

5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1

Exemple de Sortie 2

Aucun

Implémentation en C++

Voici une solution utilisant l'algorithme Union-Find pour grouper les suspects, avec des noms de variables et une structure modifiés pour la clarté.

#include <bits/stdc++.h>
using namespace std;

const int TAILLE_MAX = 1010;
int seuilK, nbPersonnes, nbAppels;
int appels[TAILLE_MAX][TAILLE_MAX]; // Matrice de durées cumulées
vector<int> listeSuspects;
map<int, vector<int>> groupes;

struct UnionTrouve {
    vector<int> parent, profondeur;
    UnionTrouve(int n) {
        parent.resize(n + 1);
        profondeur.assign(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    int chercher(int x) {
        return parent[x] == x ? x : parent[x] = chercher(parent[x]);
    }
    void fusionner(int a, int b) {
        int ra = chercher(a), rb = chercher(b);
        if (ra == rb) return;
        if (profondeur[ra] < profondeur[rb]) parent[ra] = rb;
        else if (profondeur[ra] > profondeur[rb]) parent[rb] = ra;
        else { parent[rb] = ra; profondeur[ra]++; }
    }
};

int main() {
    cin >> seuilK >> nbPersonnes >> nbAppels;
    memset(appels, 0, sizeof(appels));

    for (int i = 0; i < nbAppels; i++) {
        int src, dest, mins;
        cin >> src >> dest >> mins;
        appels[src][dest] += mins;
    }

    for (int i = 1; i <= nbPersonnes; i++) {
        int totalCourts = 0, rappels = 0;
        for (int j = 1; j <= nbPersonnes; j++) {
            if (appels[i][j] > 0 && appels[i][j] <= 5) {
                totalCourts++;
                if (appels[j][i] > 0) rappels++;
            }
        }
        if (totalCourts > seuilK && (rappels * 1.0 / totalCourts) <= 0.2) {
            listeSuspects.push_back(i);
        }
    }

    UnionTrouve structure(nbPersonnes);
    for (size_t i = 0; i < listeSuspects.size(); i++) {
        for (size_t j = i + 1; j < listeSuspects.size(); j++) {
            int s1 = listeSuspects[i], s2 = listeSuspects[j];
            if (appels[s1][s2] > 0 && appels[s2][s1] > 0) {
                structure.fusionner(s1, s2);
            }
        }
    }

    for (int suspect : listeSuspects) {
        int racine = structure.chercher(suspect);
        groupes[racine].push_back(suspect);
    }

    if (groupes.empty()) {
        cout << "Aucun" << endl;
    } else {
        for (auto& paire : groupes) {
            vector<int>& membres = paire.second;
            sort(membres.begin(), membres.end());
            for (size_t idx = 0; idx < membres.size(); idx++) {
                if (idx) cout << " ";
                cout << membres[idx];
            }
            cout << endl;
        }
    }

    return 0;
}