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
Entrée :
n = 5
edges = [
[0, 1],
[1, 2],
[2, 0],
[3, 4]
]
Sortie attendue :
expected = 3Entré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.
Entrée :
n = 3
edges = [
[0, 1],
[1, 0],
[1, 2],
[2, 1]
]
Sortie attendue :
expected = 1Entré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.