0060-ir-vir

id: 60 name: "Ir e Vir" slug: "ir-e-vir" idBeecrowd: 1318 authorSlugProblem: "beecrowd" origin: "Beecrowd 1318" difficultyLevelId: "B" description: | Dada uma rede de cidades conectadas por estradas de mão única ou mão dupla, determine quantas cidades possuem a propriedade de que é possível sair delas, visitar todas as outras cidades e retornar à cidade de origem. O problema exige a modelagem de um grafo dirigido e a identificação de componentes fortemente conexos. editorial: | **Briefing:** Pré-requisitos incluem grafos dirigidos, busca em profundidade (DFS) e o conceito de componentes fortemente conexos (SCC). Adequado para disciplinas de Algoritmos em Grafos, nível intermediário-avançado. **Estratégia:** Modele as estradas como arestas dirigidas (P=1 → uma aresta, P=2 → duas arestas). O problema se reduz a verificar se todas as cidades formam um único SCC. Se sim, resposta = N; se não, resposta = 0. **Técnica:** Algoritmo de Tarjan (DFS com low-link values) em O(V + E). Alternativamente, Kosaraju (duas DFS: uma no grafo e outra no transposto). **Edge cases:** N=1 M=0 (trivialmente SCC), grafo linear sem retorno (múltiplos SCCs), componentes desconexos, reset entre múltiplos casos de teste. timeComplexity: "O(V + E)" timeLimitSegs: 2 memoryLimitMb: 256 successmsg: "🏙️ Parabéns! Você dominou a arte de navegar entre cidades — indo e vindo por todos os caminhos possíveis!" skills: - name: "Grafos" slug: "grafos" points: 1 - name: "Componentes Fortemente Conexos" slug: "strongly-connected-components" points: 1 - name: "Busca em Profundidade" slug: "busca-profundidade" points: 1 thematicSkills: - skillSlug: "graph-theory" - skillSlug: "urban-logistics" - skillSlug: "traffic-cities" statements: - id: "a-ir-vir" testScenarioLevel: "A" files: - filename: "a_pt_ir-vir.md" level: "A" lang: "pt" - filename: "b_pt_ir-vir.pdf" level: "B" lang: "pt" type: "legacy" - filename: "c_pt_ir-vir.md" level: "C" lang: "pt" - filename: "d_pt_ir-vir.md" level: "D" lang: "pt" solutions: - id: "a-otima-tarjan-scc" level: "A" description: "Solução ótima usando Algoritmo de Tarjan para encontrar SCCs em O(V+E)" paradigm: "SCC - Tarjan" implementations: - language: "Cpp" filename: "ir-vir.cpp" - id: "b-subotima-dfs-transposto" level: "B" description: "Soluções alternativas usando DFS + Grafo Transposto (Kosaraju simplificado) e BFS" paradigm: "DFS dupla / BFS" implementations: - language: "Cpp" filename: "ir-vir.cpp" - language: "C" filename: "ir-vir.c" - language: "Java" filename: "IrEVir2.java" - language: "Python" filename: "ir-vir.py" testScenarios: - id: "d-sample" level: "D" description: "Exemplos do enunciado — ciclo simples, desconexo, misto" testType: "SAMPLE" testCount: 3 thematicSkills: - skill: "grafos" points: 1 - id: "main" level: "A" description: "Testes principais com casos variados incluindo SCC completo, parcial e edge case N=1" testType: "TDD" testCount: 5 thematicSkills: - skill: "grafos" points: 1 - skill: "strongly-connected-components" points: 1 - id: "c-edge-cases" level: "C" description: "Cenários de erro comuns — N=1 sem arestas, cadeia linear, grafo desconexo, P=2 isolado, múltiplos casos" testType: "TDD" testCount: 5 thematicSkills: - skill: "grafos" points: 1 - skill: "strongly-connected-components" points: 1