Tous les défis
Difficile 1 résolu 100.0 % de réussite

Composantes fortement connexes

Comptez les groupes de nœuds pouvant tous s’atteindre mutuellement.

Ce que vous allez apprendre

  • Trouver les groupes de nœuds mutuellement accessibles
  • Utiliser l'ordre de fin du DFS ou les valeurs low-link
  • Travailler avec des graphes orientés

Problème

Dans un graphe orienté avec des nœuds numérotés de 0 à n−1, une composante fortement connexe est un groupe maximal de nœuds où chaque nœud peut atteindre tous les autres. Comptez le nombre de ces composantes (algorithme de Kosaraju ou de Tarjan).

Implémentez count_scc(n, edges).

Entrée

n : Le nombre de nœuds. edges : Arêtes orientées sous la forme [from, to].

Sortie

Retournez le nombre de composantes.

Contraintes

1 ≤ n ≤ 100 000 ; 0 ≤ edges ≤ 200 000

Exemples

Exemple 1
Entrée :
n = 5
edges = [
    [0, 1],
    [1, 2],
    [2, 0],
    [3, 4]
]

Sortie attendue :
expected = 3
Entrée :
long long n = 5;
std::vector<std::vector<long long>> edges = {
    {0, 1},
    {1, 2},
    {2, 0},
    {3, 4}
};

Sortie attendue :
long long expected = 3;
Entrée :
long n = 5;
long[][] edges = new long[][] {
    new long[] {0, 1},
    new long[] {1, 2},
    new long[] {2, 0},
    new long[] {3, 4}
};

Sortie attendue :
long expected = 3;

Explication

0, 1, 2 forment un cycle (une seule composante) ; 3 et 4 ne peuvent pas s’atteindre mutuellement, donc ils sont séparés : 3.

Exemple 2
Entrée :
n = 3
edges = [
    [0, 1],
    [1, 0],
    [1, 2],
    [2, 1]
]

Sortie attendue :
expected = 1
Entrée :
long long n = 3;
std::vector<std::vector<long long>> edges = {
    {0, 1},
    {1, 0},
    {1, 2},
    {2, 1}
};

Sortie attendue :
long long expected = 1;
Entrée :
long n = 3;
long[][] edges = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0},
    new long[] {1, 2},
    new long[] {2, 1}
};

Sortie attendue :
long expected = 1;

Explication

Les trois nœuds peuvent tous s’atteindre : 1.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Un nœud appartient avec un autre seulement si chacun peut atteindre l’autre ; pense donc en régions mutuellement atteignables plutôt qu’en simple portée.

Indice 2

Utilise un ordre de parcours sur le graphe original, puis explore le graphe inversé pour récupérer une région à la fois.

Indice 3

Fais attention à l’ordre de fin et aux nœuds isolés ; chaque nœud doit être affecté exactement une fois, même sans arêtes entrantes ni sortantes.

Complexité attendue

temps O(n + m), espace supplémentaire O(n + m)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 825 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.