0642-dinastias-sao-peterburg

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 642 name: "Dinastias de São Petersburgo" slug: "dinastias-sao-peterburg" timelimit: 1.0 memlimit: 256 difficultyLevelId: D author: Unknown origin: Mundo do Código description: 'Dado N nobres e M relações pai→filho, encontre o número mínimo de dinastias para cobrir todos os nobres (Minimum Path Cover via Maximum Bipartite Matching).' editorial: | O problema pede o número mínimo de caminhos (dinastias) que cobrem todos os vértices de um grafo dirigido. Pelo teorema de König, Minimum Path Cover = N − Maximum Matching no grafo bipartido associado. Para cada aresta u→v do grafo original, criamos a aresta u_L → v_R no bipartido. O matching máximo é encontrado pelo algoritmo de Kuhn (augmenting paths via DFS), resultando em complexidade O(N × M) no pior caso, o que é confortável dentro dos limites. successmsg: 'Excelente! Minimum Path Cover via Maximum Bipartite Matching — domínio de grafos bipartidos!' timeComplexity: O(N × M) skills: - grafos - bipartido - max-flow tags: [] statements: - id: a-dinastias-sao-peterburg testScenarioLevel: A thematicSkills: - skill: history points: 1 - skill: grafos points: 2 testScenarios: - id: a-performance name: Teste de Desempenho description: Casos máximos com N=2000 e grafos esparsos/densos. helpTip: 'Certifique-se de que o Kuhn roda em tempo hábil para N=2000.' level: A testType: PERFORMANCE skills: - skill: bipartido points: 2 - id: b-fuzzing name: Fuzzing Aleatório description: Casos aleatórios variando N e M para estresse. helpTip: 'Teste com grafos de diferentes densidades.' level: B testType: TDD skills: - skill: grafos points: 1 - id: c-edge name: Casos Extremos description: Grafo mínimo, sem arestas, estrela, cadeia, cadeias paralelas. helpTip: 'Funciona quando N=1? E quando não há arestas?' level: C testType: TDD skills: - skill: grafos points: 1 - id: d-sample name: Exemplos do Enunciado description: Casos de teste presentes no enunciado original. helpTip: 'Sua solução deve passar no exemplo básico.' level: D testType: TDD skills: - skill: io points: 1 solutions: - id: a-otima-basica name: Kuhn (Matching Máximo) description: Minimum Path Cover via Maximum Bipartite Matching usando algoritmo de Kuhn. O(N*M). level: A implementations: - language: cpp paradigm: Imperative main: dinastias.cpp filenames: - dinastias.cpp - language: py paradigm: Imperative main: dinastias.py filenames: - dinastias.py - language: java paradigm: OO main: Dinastias filenames: - Dinastias.java - id: b-subotima-brute-force name: Greedy Chain Building description: Solução gulosa que monta cadeias greedily sem matching ótimo. Pode dar WA em grafos complexos. level: B implementations: - language: py paradigm: Imperative main: brute_force.py filenames: - brute_force.py authorSlugProblem: Unknown