Listas de Adjacência a partir da Entrada
Construa o grafo fornecido pelas competições.
Listas de Adjacência a partir da Entrada é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é realmente um grafo
Um grafo é simplesmente formado por pontos chamados nós, ligados por linhas chamadas arestas. Cidades conectadas por estradas formam um grafo que você já conhece. 🗺️
Nós e arestas
Cada nó representa algo, e cada aresta indica que dois nós estão conectados. Em competições, os nós geralmente são numerados de 1 a n.
A lista de adjacências
A estrutura de armazenamento mais usada em competições é a lista de adjacências: para cada nó, mantenha uma lista de seus vizinhos diretos.
adj = [[] for _ in range(n + 1)]Por que não uma matriz
Uma matriz usa memória proporcional a n ao quadrado, o que se torna inviável para valores grandes de n. Uma lista de adjacências armazena apenas as arestas existentes, portanto escala melhor.
Ler a primeira linha
A maioria das entradas começa com dois números: n nós e m arestas. Leia-os primeiro para saber quantas arestas esperar.
n, m = map(int, input().split())Uma aresta por linha
Cada uma das próximas m linhas fornece um par u v. Essa única aresta significa que u e v estão diretamente conectados.
u, v = map(int, input().split())Não direcionada significa nos dois sentidos
Para uma aresta não direcionada, adicione a ligação nas duas direções. Você pode ir de u para v e de v para u.
adj[u].append(v)
adj[v].append(u)Direcionada significa em um só sentido
Para uma aresta direcionada, armazene apenas a ligação de u para v. Leia o enunciado com atenção para saber qual tipo você tem.
adj[u].append(v)Construí-la em um laço
Repita m vezes, leia cada par e preencha as listas. Ao final do laço, sua lista de adjacências conterá o grafo inteiro.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Indexação a partir de 1 ou de 0
Se os nós começarem em 1, dimensione sua lista como n mais 1 para que o índice n seja válido. Confundir a indexação causa erros silenciosos.
Visitar os vizinhos de um nó
Depois de construída, a exploração é simples: percorra a lista de adjacências de um nó para alcançar cada vizinho em uma única etapa.
for nb in adj[u]:
print(nb)Verificação rápida
Você leu uma aresta não direcionada u v. O que deve armazenar?
Recapitulação
Agora você constrói um grafo como uma lista de adjacências: lê n e m, percorre as arestas e adiciona as duas direções quando a aresta não é direcionada. 🎉
Perguntas Frequentes
A aula “Listas de Adjacência a partir da Entrada” é grátis?
Sim — o texto completo de “Listas de Adjacência a partir da Entrada” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Listas de Adjacência a partir da Entrada”?
Construa o grafo fornecido pelas competições. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Listas de Adjacência a partir da Entrada”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Listas de Adjacência a partir da Entrada
- BFS para Caminhos Mínimos sem Pesos
- DFS, Recursão e Pilhas Iterativas
- Componentes Conexos e Preenchimento por Inundação