Cercles d'amis

Problème des cercles d'amis

Il y a N étudiants dans une classe, chaque étudiant peut avoir 0 ou plusieurs amis. Si A est un ami de B et B est un ami de C, alors A et C sont également des amis (relation transitive).

Nous définissons un cercle d'amis comme un groupe d'élèves amis, tel que défini par la relation transitive ci-dessus.

Étant donné une matrice friends de taille NxN constituée des caractères 'Y' ou 'N'. Si friends[i][j] = 'Y', alors les i-ème et j-ème étudiants sont des amis, sinon 'N'.

Figure : Exemple de relations d'amitié et leur représentation matricielle

Problème

Compter les cercles d'amis

Niveau : Intermédiaire

Trouvez le nombre total de cercles d'amis dans la classe.

Exemple

Entrée

friends = [
    ['Y', 'Y', 'N', 'N'],
    ['Y', 'Y', 'Y', 'N'],
    ['N', 'Y', 'Y', 'N'],
    ['N', 'N', 'N', 'Y']
]

Sortie

Explication : Les étudiants 0,1,2 forment un cercle (car 0-1 sont amis, 1-2 sont amis), et l'étudiant 3 est isolé et forme un cercle à lui seul.

Solution détaillée

Idée clé — Parcours en profondeur (DFS)

Le problème revient à trouver le nombre de composantes connexes dans un graphe non orienté où les sommets sont les étudiants et les arêtes représentent les relations d'amitié.

Algorithme

Initialiser un tableau visited pour marquer les étudiants déjà visités.
Initialiser le compteur de cercles NC = 0.
Pour chaque étudiant i de 0 à N-1 :
- Si l'étudiant i n'est pas encore visité, c'est le début d'un nouveau cercle.
- Lancer un parcours en profondeur (DFS) à partir de i pour marquer tous ses amis (directs et indirects).
- Incémenter le compteur NC += 1.
Retourner NC.

Algorithme compter_cercles(friends):
    N ← taille(friends)
    visited ← tableau de booléens de taille N, initialisé à False
    nb_cercles ← 0
    
    Pour i de 0 à N-1:
        Si visited[i] == False:
            DFS(i, visited)
            nb_cercles ← nb_cercles + 1
    
    Retourner nb_cercles


Fonction DFS(i, visited):
    visited[i] ← True
    Pour j de 0 à N-1:
        Si friends[i][j] == 'Y' et i != j et visited[j] == False:
            DFS(j, visited)

def compter_cercles(friends):
    """
    Compte le nombre de cercles d'amis dans une classe.
    
    Paramètres:
        friends: matrice NxN avec 'Y' ou 'N' indiquant les relations d'amitié
        
    Retourne:
        Le nombre de cercles d'amis (composantes connexes)
    """
    N = len(friends)
    visited = [False] * N
    nb_cercles = 0
    
    def dfs(i):
        """Parcours en profondeur à partir de l'étudiant i"""
        visited[i] = True
        for j in range(N):
            # Si j est ami avec i, différent de i, et non visité
            if friends[i][j] == 'Y' and i != j and not visited[j]:
                dfs(j)
    
    # Parcourir tous les étudiants
    for i in range(N):
        if not visited[i]:
            dfs(i)          # Marquer tout le cercle d'amis
            nb_cercles += 1  # Un nouveau cercle trouvé
    
    return nb_cercles


# Exemple d'utilisation
friends = [
    ['Y', 'Y', 'N', 'N'],
    ['Y', 'Y', 'Y', 'N'],
    ['N', 'Y', 'Y', 'N'],
    ['N', 'N', 'N', 'Y']
]

print(f"Nombre de cercles d'amis : {compter_cercles(friends)}")

Sortie

Nombre de cercles d'amis : 2

Complexité

Temps : O(N²) dans le pire cas, car nous parcourons la matrice pour chaque étudiant.
Espace : O(N) pour le tableau visited et la pile de récursion.

Solution alternative : Union-Find (Disjoint Sets)

Optimisation

Approche avec Union-Find

Une autre approche pour résoudre ce problème est d'utiliser la structure de données Union-Find (ou Disjoint Set Union), qui permet de gérer efficacement les relations d'équivalence.

Solution avec Union-Find

Idée clé — Union-Find

L'Union-Find est une structure qui maintient des ensembles disjoints et permet de fusionner des ensembles efficacement.

Initialement, chaque étudiant est dans son propre ensemble.
Pour chaque paire (i, j) où friends[i][j] = 'Y', on fusionne les ensembles de i et j.
À la fin, le nombre d'ensembles distincts est le nombre de cercles.

class UnionFind:
    """Structure Union-Find avec compression de chemin et union par rang"""
    
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # Nombre d'ensembles distincts
    
    def find(self, x):
        """Trouve le représentant de x (avec compression de chemin)"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """Fusionne les ensembles contenant x et y"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        
        # Union par rang
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        
        self.count -= 1  # Un ensemble de moins


def compter_cercles_union_find(friends):
    """
    Compte le nombre de cercles d'amis avec Union-Find
    """
    N = len(friends)
    uf = UnionFind(N)
    
    # Parcourir la moitié supérieure de la matrice (éviter les doublons)
    for i in range(N):
        for j in range(i + 1, N):
            if friends[i][j] == 'Y':
                uf.union(i, j)
    
    return uf.count


# Test
friends = [
    ['Y', 'Y', 'N', 'N'],
    ['Y', 'Y', 'Y', 'N'],
    ['N', 'Y', 'Y', 'N'],
    ['N', 'N', 'N', 'Y']
]

print(f"Nombre de cercles (Union-Find) : {compter_cercles_union_find(friends)}")

Sortie

Nombre de cercles (Union-Find) : 2

Complexité

Temps : O(N² × α(N)), où α(N) est la fonction inverse d'Ackermann (presque constant).
Espace : O(N) pour les tableaux parent et rank.

Autre exemple

Entrée

friends = [
    ['Y', 'N', 'N', 'N'],
    ['N', 'Y', 'N', 'N'],
    ['N', 'N', 'Y', 'N'],
    ['N', 'N', 'N', 'Y']
]

Sortie

Explication : Aucun étudiant n'est ami avec un autre. Chacun forme son propre cercle.

Contraintes

1 ≤ N ≤ 10³
La matrice est symétrique (l'amitié est une relation symétrique)
friends[i][i] peut être 'Y' ou 'N' (généralement 'N' car on ne se compte pas soi-même)

Comparaison des approches

Approche	Complexité temporelle	Complexité spatiale	Avantages
DFS / BFS	O(N²)	O(N)	Simple à implémenter, parcourt tout le graphe
Union-Find	O(N² × α(N))	O(N)	Très efficace, évite la récursion

Points clés à retenir

Le problème des cercles d'amis revient à trouver les composantes connexes d'un graphe.
Deux approches principales : parcours (DFS/BFS) ou Union-Find.
La matrice d'adjacence est symétrique car l'amitié est une relation réciproque.
La relation d'amitié est transitive (amis d'amis = amis).
Un étudiant isolé forme son propre cercle.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Exercices python récursivité Tableaux Complexité analyse des algorithmes

Précédent Plus courts chemins entre toutes les paires de sommets …

Suivant Trouvez le nombre d'îles ou de grappes (clusters)

Problème des cercles d'amis

Compter les cercles d'amis

Algorithme

Solution alternative : Union-Find (Disjoint Sets)

Approche avec Union-Find

Comparaison des approches

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Cercles d'amis

Problème des cercles d'amis

Compter les cercles d'amis

Algorithme

Solution alternative : Union-Find (Disjoint Sets)

Approche avec Union-Find

Comparaison des approches

Discussion (0)

Laisser un commentaire