Problème
Afficher l’original (anglais)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 = 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.
Exemple 2
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.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.