Listes d’adjacence à partir de l’entrée
Construire le graphe fourni par les concours
Listes d’adjacence à partir de l’entrée est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Ce qu’est vraiment un graphe
Un graphe est simplement constitué de points appelés nœuds, reliés par des traits appelés arêtes. Les villes reliées par des routes forment un graphe que vous connaissez déjà. 🗺️
Nœuds et arêtes
Chaque nœud représente une entité, et chaque arête indique que deux nœuds sont connectés. Dans les concours, les graphes numérotent généralement les nœuds de 1 à n.
La liste d’adjacence
La structure de stockage privilégiée dans les concours est la liste d’adjacence : pour chaque nœud, conservez la liste de ses voisins directs.
adj = [[] for _ in range(n + 1)]Pourquoi pas une matrice
Une matrice utilise n au carré emplacements mémoire, ce qui devient énorme pour de grandes valeurs de n. Une liste d’adjacence ne stocke que les arêtes qui existent, ce qui lui permet de passer à l’échelle.
Lire la première ligne
La plupart des entrées commencent par deux nombres : n nœuds et m arêtes. Lisez-les d’abord afin de savoir combien d’arêtes vous devez attendre.
n, m = map(int, input().split())Une arête par ligne
Chacune des m lignes suivantes fournit une paire u v. Cette seule arête signifie que u et v sont directement connectés.
u, v = map(int, input().split())Non orienté signifie dans les deux sens
Pour une arête non orientée, ajoutez la liaison dans les deux sens. Vous pouvez aller de u vers v et de v vers u.
adj[u].append(v)
adj[v].append(u)Orienté signifie dans un seul sens
Pour une arête orientée, stockez uniquement la liaison de u vers v. Lisez attentivement l’énoncé pour savoir de quel type d’arête il s’agit.
adj[u].append(v)La construire dans une boucle
Répétez m fois, lisez chaque paire et remplissez les listes. À la fin de la boucle, votre liste d’adjacence contient tout le graphe.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indexation à partir de 1 ou de 0
Si les nœuds commencent à 1, dimensionnez votre liste à n plus 1 afin que l’indice n soit valide. Confondre les modes d’indexation provoque des erreurs silencieuses.
Parcourir les voisins d’un nœud
Une fois la structure construite, l’exploration est simple : parcourez la liste des voisins d’un nœud pour atteindre chaque voisin en une étape.
for nb in adj[u]:
print(nb)Vérification rapide
Vous lisez une arête non orientée u v. Que devez-vous stocker ?
Récapitulatif
Vous savez maintenant construire un graphe sous forme de liste d’adjacence : lisez n et m, parcourez les arêtes et ajoutez les deux sens lorsqu’elles sont non orientées. 🎉
Questions Fréquemment Posées
La leçon « Listes d’adjacence à partir de l’entrée » est-elle gratuite ?
Oui — le texte complet de « Listes d’adjacence à partir de l’entrée » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Listes d’adjacence à partir de l’entrée » ?
Construire le graphe fourni par les concours Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Listes d’adjacence à partir de l’entrée » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Listes d’adjacence à partir de l’entrée
- BFS pour les plus courts chemins non pondérés
- DFS, récursion et piles itératives
- Composantes connexes et remplissage par diffusion