import Mathlib /-! # Redundant Connection Ii In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents. The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u_i, v_i] that represents a directed edge connecting nodes u_i and v_i, where u_i is a parent of child v_i. Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. ## Constraints - n == edges.length - 3 <= n <= 1000 - edges[i].length == 2 - 1 <= u_i, v_i <= n - u_i != v_i ## Provided examples - `edges = [[1, 2], [1, 3], [2, 3]]` → `[2, 3]` - `edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]` → `[4, 1]` - `edges = [[1, 2], [2, 3], [3, 1]]` → `[3, 1]` ## Synthesized negative examples - invalid input: `edges = [[1, 2], [2, 1]]` ([structural] a predicate that admits 3 <= n <= 1000. only two edges; a predicate checking only edge contents accepts it) - invalid input: `edges = [[1, 2], [2, 3], [1]]` ([structural] a predicate that admits edges[i].length == 2. an edge with one endpoint; a predicate checking only node values accepts it) - invalid input: `edges = [[1, 2], [2, 3], [0, 3]]` ([structural] a predicate that admits 1 <= ui, vi <= n. a node labeled 0; a predicate checking only labels at most n accepts it) - `edges = [[1, 2], [1, 3], [2, 3]]` → `[1, 3]` is wrong ([structural] unattainable does not fit; a specification omitting the last-choice rule accepts this. valid removable edge, but not the one occurring last) - `edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]` → `[2, 3]` is wrong ([structural] Feasible edge accepted without requiring the latest position. removable, but [4,1] occurs later) - `edges = [[1, 2], [2, 3], [3, 1]]` → `[1, 2]` is wrong ([structural] only requires a removable edge, not the one occurring last. valid removal but not the latest valid edge) -/ namespace PRedundantConnectionIi abbrev Input := List (List Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- Adjacency in the directed graph whose edges are the two-element lists in `edges`. -/ def edgeDigraph (edges : List (List Nat)) : Digraph Nat := ⟨fun u v => [u, v] ∈ edges⟩ /-- The vertex labels `1` through `n`. -/ def vertexList (n : Nat) : List Nat := (List.range n).map (fun k => k + 1) /-- A directed graph is a rooted tree on the vertices `1` through `n`. -/ def IsRootedTree (G : Digraph Nat) (n : Nat) : Prop := ∃ root ∈ vertexList n, (∀ v ∈ vertexList n, Relation.ReflTransGen G.Adj root v) ∧ (∀ u ∈ vertexList n, ¬ G.Adj u root) ∧ (∀ v ∈ vertexList n, v ≠ root → ∃! u : Nat, u ∈ vertexList n ∧ G.Adj u v) /-- An edge is removable when it occurs in `edges` and deleting it leaves a rooted tree. -/ def IsRemovableEdge (edges : List (List Nat)) (e : List Nat) : Prop := e ∈ edges ∧ IsRootedTree (edgeDigraph edges \ edgeDigraph [e]) edges.length /-- Count the edges whose destination is `v`. -/ def incomingCount (edges : List (List Nat)) (v : Nat) : Nat := (edges.filter (fun e => match e with | [_, w] => w == v | _ => false)).length /-- Compute the vertices reachable from `root` among `1` through `n`. -/ def reachableFrom (n : Nat) (edges : List (List Nat)) (root : Nat) : List Nat := (List.range (n + 1)).foldl (fun seen _ => let fresh := (vertexList n).filter (fun v => !seen.contains v && seen.any (fun u => edges.contains [u, v])) seen ++ fresh) [root] /-! ### Validity predicate (V) -/ /-- Valid input: the stated edge bounds, labels, vertex coverage, distinctness, and rooted-tree-plus-one-edge structure. -/ def isValidInput (input : Input) : Bool := let n := input.length 3 ≤ n && n ≤ 1000 && input.all (fun e => match e with | [u, v] => 1 ≤ u && u ≤ n && 1 ≤ v && v ≤ n && u != v | _ => false) && (vertexList n).all (fun v => input.any (fun e => e.contains v)) && input.all (fun e => input.count e == 1) && input.any (fun extra => let tree := input.erase extra (vertexList n).any (fun root => incomingCount tree root == 0 && (vertexList n).all (fun v => v == root || incomingCount tree v == 1) && (vertexList n).all (fun v => (reachableFrom n tree root).contains v))) /-! ### Ideal specification (P_spec) -/ /-- `result` is the removable edge occurring last in the input order. -/ def redundantConnection_spec (input : Input) (result : Output) : Prop := ∃ i : Nat, input[i]? = some result ∧ IsGreatest {k : Nat | ∃ e : List Nat, input[k]? = some e ∧ IsRemovableEdge input e} i /-! ### Decidable specification (P_check) -/ /-- Rooted-tree check on vertices `1..n`: one root of indegree 0, every other vertex of indegree 1, and every vertex reachable from the root. -/ def isRootedTreeOn (edges : List (List Nat)) (n : Nat) : Bool := (vertexList n).any (fun root => incomingCount edges root == 0 && (vertexList n).all (fun v => v == root || incomingCount edges v == 1) && (vertexList n).all (fun v => (reachableFrom n edges root).contains v)) /-- `e` occurs in `edges`, and deleting it leaves a rooted tree on vertices `1..edges.length`. -/ def isRemovableEdge (edges : List (List Nat)) (e : List Nat) : Bool := edges.contains e && isRootedTreeOn (edges.erase e) edges.length /-- Executable checker for `redundantConnection_spec`: `result` is the removable edge occurring last in the input order. -/ def redundantConnection_check (input : Input) (result : Output) : Bool := let n := input.length (List.range n).any (fun i => input[i]? == some result && isRemovableEdge input result && (List.range n).all (fun k => match input[k]? with | some e => !(isRemovableEdge input e) || k ≤ i | none => true)) theorem root_of_bridges (input : Input) (result : Output) (bridge : ∀ e, isRemovableEdge input e ↔ IsRemovableEdge input e) : redundantConnection_check input result ↔ redundantConnection_spec input result := by simp only [redundantConnection_check, List.any_eq_true, List.mem_range, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, redundantConnection_spec, IsGreatest, mem_upperBounds, Set.mem_setOf_eq] constructor · rintro ⟨i, hi, ⟨he, hr⟩, hmax⟩ refine ⟨i, he, ⟨result, he, (bridge result).mp hr⟩, ?_⟩ rintro k ⟨e, hk, hrk⟩ have hb := (List.getElem?_eq_some_iff.mp hk).1 have hm := hmax k hb simpa [hk, (bridge e).mpr hrk] using hm · rintro ⟨i, he, ⟨e, hei, hr⟩, hmax⟩ have hi := (List.getElem?_eq_some_iff.mp he).1 have ee : e = result := by simpa [he] using hei.symm subst e refine ⟨i, hi, ⟨he, (bridge result).mpr hr⟩, ?_⟩ intro k hk cases heq : input[k]? with | none => simp | some e => by_cases hrk : isRemovableEdge input e · have hm := hmax k ⟨e, heq, (bridge e).mp hrk⟩ simpa [hrk] using hm · simp [hrk] /- Insert as helper declarations after `import Mathlib`. Directed finite reachability needs neither symmetry nor a decreasing rank. The finite carrier, semantic step reflection, preservation, and agreement with the frozen checker's retained iterations remain adapter obligations. This file alone does not prove any generated checker/specification theorem. -/ namespace WxEconomy /-- Exactly `n` directed steps, including equality at zero. -/ def wxExactSteps {α : Type*} (R : α → α → Prop) : Nat → α → α → Prop | 0, a, b => a = b | n + 1, a, b => ∃ c, wxExactSteps R n a c ∧ R c b theorem wx_exactSteps_sound {α : Type*} {R : α → α → Prop} {n : Nat} {a b : α} (h : wxExactSteps R n a b) : Relation.ReflTransGen R a b := by induction n generalizing b with | zero => exact h ▸ Relation.ReflTransGen.refl | succ n ih => obtain ⟨c, hc, hb⟩ := h exact (ih hc).tail hb /-- The pinned legacy spelling is definitionally the current chain predicate. -/ theorem wx_chainPrime_iff_isChain {α : Type*} (R : α → α → Prop) (l : List α) : List.Chain' R l ↔ List.IsChain R l := Iff.rfl private theorem wx_exactSteps_prepend {α : Type*} {R : α → α → Prop} {n : Nat} {a b c : α} (edge : R a b) (path : wxExactSteps R n b c) : wxExactSteps R (n + 1) a c := by induction n generalizing c with | zero => exact ⟨a, rfl, path ▸ edge⟩ | succ n ih => obtain ⟨d, path, last⟩ := path exact ⟨d, ih path, last⟩ /-- A nonempty chain has `tail.length` edges; a singleton has zero edges. -/ theorem wx_isChain_exactSteps {α : Type*} {R : α → α → Prop} {a : α} (tail : List α) (chain : List.IsChain R (a :: tail)) : wxExactSteps R tail.length a ((a :: tail).getLast (List.cons_ne_nil _ _)) := by induction tail generalizing a with | nil => rfl | cons c tail ih => obtain ⟨edge, chain⟩ := List.isChain_cons_cons.mp chain simpa only [List.length_cons, List.getLast_cons_cons] using wx_exactSteps_prepend edge (ih (a := c) chain) /-- Convert in either direction without losing the start, end, or edge count. The witness is the tail of the nonempty vertex list, including the endpoint. -/ theorem wx_exactSteps_iff_isChain {α : Type*} {R : α → α → Prop} (n : Nat) (a b : α) : wxExactSteps R n a b ↔ ∃ tail : List α, tail.length = n ∧ List.IsChain R (a :: tail) ∧ (a :: tail).getLast (List.cons_ne_nil _ _) = b := by constructor · intro path induction n generalizing b with | zero => exact ⟨[], rfl, .singleton a, path⟩ | succ n ih => obtain ⟨c, path, edge⟩ := path obtain ⟨tail, length, chain, finish⟩ := ih c path refine ⟨tail ++ [b], by simp [length], ?_, ?_⟩ · simpa only [List.cons_append] using chain.append (.singleton b) (by simpa [List.getLast?_eq_getLast_of_ne_nil (List.cons_ne_nil a tail), finish] using edge) · simp only [← List.cons_append, List.getLast_concat] · rintro ⟨tail, rfl, chain, rfl⟩ exact wx_isChain_exactSteps tail chain /-- A finite retained-growth recurrence is complete after `card α` rounds. The recurrence must describe the actual frozen iterations on this carrier. -/ theorem wx_finite_retained_complete {α : Type*} [Fintype α] (R : α → α → Prop) (states : Nat → Finset α) (grow : ∀ n b, b ∈ states (n + 1) ↔ b ∈ states n ∨ ∃ c ∈ states n, R c b) (a b : α) (seed : a ∈ states 0) (reachable : Relation.ReflTransGen R a b) : b ∈ states (Fintype.card α) := by classical have keep : ∀ n, states n ⊆ states (n + 1) := by intro n c hc exact (grow n c).mpr (Or.inl hc) have propagate : ∀ n, states n = states (n + 1) → states (n + 1) = states (n + 2) := by intro n hn ext c rw [grow (n + 1) c, ← hn, ← grow n c, hn] have dichotomy : ∀ n, states n = states (n + 1) ∨ n < (states n).card := by intro n induction n with | zero => exact Or.inr (Finset.card_pos.mpr ⟨a, seed⟩) | succ n ih => rcases ih with stable | large · exact Or.inl (propagate n stable) · by_cases stable : states n = states (n + 1) · exact Or.inl (propagate n stable) · have strict : (states n).card < (states (n + 1)).card := Finset.card_lt_card (ssubset_iff_subset_ne.mpr ⟨keep n, stable⟩) exact Or.inr (by omega) have stable : states (Fintype.card α) = states (Fintype.card α + 1) := by rcases dichotomy (Fintype.card α) with stable | impossible · exact stable · have bound := Finset.card_le_univ (states (Fintype.card α)) omega have initial : a ∈ states (Fintype.card α) := by have all : ∀ n, a ∈ states n := by intro n induction n with | zero => exact seed | succ n ih => exact keep n ih exact all _ induction reachable with | refl => exact initial | tail _ edge ih => rw [stable] exact (grow _ _).mpr (Or.inr ⟨_, ih, edge⟩) private theorem wx_boundedSteps_succ {α : Type*} (R : α → α → Prop) (n : Nat) (a b : α) : (∃ k ≤ n + 1, wxExactSteps R k a b) ↔ (∃ k ≤ n, wxExactSteps R k a b) ∨ ∃ c, (∃ k ≤ n, wxExactSteps R k a c) ∧ R c b := by constructor · rintro ⟨k, hk, path⟩ by_cases old : k ≤ n · exact Or.inl ⟨k, old, path⟩ · have eq : k = n + 1 := by omega subst k obtain ⟨c, hc, hb⟩ := path exact Or.inr ⟨c, ⟨n, le_rfl, hc⟩, hb⟩ · rintro (⟨k, hk, path⟩ | ⟨c, ⟨k, hk, path⟩, edge⟩) · exact ⟨k, by omega, path⟩ · exact ⟨k + 1, by omega, c, path, edge⟩ /-- Cycles can be removed sufficiently to obtain at most `card α` steps. The relation is arbitrary and directed; no shortest-path premise is assumed. -/ theorem wx_reachable_iff_bounded {α : Type*} [Fintype α] (R : α → α → Prop) (a b : α) : Relation.ReflTransGen R a b ↔ ∃ n ≤ Fintype.card α, wxExactSteps R n a b := by classical constructor · intro reachable let states (n : Nat) : Finset α := Finset.univ.filter (fun c => ∃ k ≤ n, wxExactSteps R k a c) have member : ∀ n c, c ∈ states n ↔ ∃ k ≤ n, wxExactSteps R k a c := by intro n c simp [states] have grow : ∀ n c, c ∈ states (n + 1) ↔ c ∈ states n ∨ ∃ d ∈ states n, R d c := by intro n c simp only [member, wx_boundedSteps_succ] have seed : a ∈ states 0 := (member 0 a).mpr ⟨0, le_rfl, rfl⟩ exact (member _ b).mp (wx_finite_retained_complete R states grow a b seed reachable) · rintro ⟨n, _, path⟩ exact wx_exactSteps_sound path theorem wx_exactSteps_map {α β : Type*} {R : α → α → Prop} {S : β → β → Prop} (f : α → β) (step : ∀ a b, R a b → S (f a) (f b)) {n : Nat} {a b : α} (path : wxExactSteps R n a b) : wxExactSteps S n (f a) (f b) := by induction n generalizing b with | zero => exact congrArg f path | succ n ih => obtain ⟨c, hc, hb⟩ := path exact ⟨f c, ih hc, step c b hb⟩ /-- Restrict an ambient reachability proof to an invariant finite carrier. The caller must prove preservation for every semantic step from the carrier. -/ theorem wx_reachable_bounded_on {α : Type*} (P : α → Prop) [Fintype {a // P a}] (R : α → α → Prop) (preserve : ∀ a b, P a → R a b → P b) {a b : α} (start : P a) (reachable : Relation.ReflTransGen R a b) : P b ∧ ∃ n ≤ Fintype.card {a // P a}, wxExactSteps R n a b := by have restricted : ∃ finish : P b, Relation.ReflTransGen (fun x y : {a // P a} => R x.val y.val) ⟨a, start⟩ ⟨b, finish⟩ := by induction reachable with | refl => exact ⟨start, .refl⟩ | tail _ edge ih => obtain ⟨middle, path⟩ := ih exact ⟨preserve _ _ middle edge, path.tail edge⟩ obtain ⟨finish, path⟩ := restricted obtain ⟨n, bound, exactPath⟩ := (wx_reachable_iff_bounded (fun x y : {a // P a} => R x.val y.val) ⟨a, start⟩ ⟨b, finish⟩).mp path exact ⟨finish, n, bound, wx_exactSteps_map Subtype.val (fun _ _ edge => edge) exactPath⟩ /-- Explicitly enumerate a bounded Nat carrier through `Fin bound`. -/ def wxFinEquivNatLt (bound : Nat) : Fin bound ≃ {a : Nat // a < bound} where toFun a := ⟨a.val, a.isLt⟩ invFun a := ⟨a.val, a.property⟩ left_inv _ := rfl right_inv _ := rfl /-- Install locally with `letI := wxNatLtFintype bound`; no global instance. -/ abbrev wxNatLtFintype (bound : Nat) : Fintype {a : Nat // a < bound} := Fintype.ofEquiv (Fin bound) (wxFinEquivNatLt bound) theorem wx_natLt_card (bound : Nat) [Fintype {a : Nat // a < bound}] : Fintype.card {a : Nat // a < bound} = bound := (Fintype.card_congr (wxFinEquivNatLt bound)).symm.trans (Fintype.card_fin bound) /-- Bounded Nat reachability with the finite carrier and its card discharged. Semantic preservation of the chosen bound is still a caller obligation. -/ theorem wx_reachable_bounded_nat (bound : Nat) (R : Nat → Nat → Prop) (preserve : ∀ a b, a < bound → R a b → b < bound) {a b : Nat} (start : a < bound) (reachable : Relation.ReflTransGen R a b) : b < bound ∧ ∃ n ≤ bound, wxExactSteps R n a b := by letI := wxNatLtFintype bound simpa only [wx_natLt_card] using wx_reachable_bounded_on (fun a => a < bound) R preserve start reachable end WxEconomy def rcGrow (n : Nat) (edges : List (List Nat)) (seen : List Nat) : List Nat := seen ++ (vertexList n).filter (fun v => !seen.contains v && seen.any (fun u => edges.contains [u,v])) def rcIter (n : Nat) (edges : List (List Nat)) (root : Nat) : Nat → List Nat | 0 => [root] | k+1 => rcGrow n edges (rcIter n edges root k) lemma rc_grow_mem (n : Nat) (edges : List (List Nat)) (seen : List Nat) (v : Nat) : v ∈ rcGrow n edges seen ↔ v ∈ seen ∨ v ∈ vertexList n ∧ ∃ u ∈ seen, [u,v] ∈ edges := by simp only [rcGrow, List.mem_append, List.mem_filter, Bool.and_eq_true, Bool.not_eq_true', Bool.eq_false_iff, ne_eq, List.any_eq_true, List.contains_iff] tauto lemma rc_iter_sound (n : Nat) (edges : List (List Nat)) (root k v : Nat) (hv : v ∈ rcIter n edges root k) : Relation.ReflTransGen (edgeDigraph edges).Adj root v := by induction k generalizing v with | zero => have he : v = root := by simpa [rcIter] using hv subst v exact .refl | succ k ih => rw [rcIter, rc_grow_mem] at hv rcases hv with hv | ⟨_, u, hu, he⟩ · exact ih v hv · exact (ih u hu).tail he lemma rc_iter_complete (n : Nat) (edges : List (List Nat)) (root : Nat) (bound : ∀ a b, [a,b] ∈ edges → b ∈ vertexList n) (k v : Nat) (path : WxEconomy.wxExactSteps (edgeDigraph edges).Adj k root v) : v ∈ rcIter n edges root k := by induction k generalizing v with | zero => have he : root = v := path simp [rcIter, he] | succ k ih => obtain ⟨u, hu, he⟩ := path rw [rcIter, rc_grow_mem] exact Or.inr ⟨bound u v he, u, ih u hu, he⟩ lemma rc_iter_mono (n : Nat) (edges : List (List Nat)) (root k m v : Nat) (hkm : k ≤ m) (hv : v ∈ rcIter n edges root k) : v ∈ rcIter n edges root m := by induction m, hkm using Nat.le_induction with | base => exact hv | succ m hm ih => rw [rcIter, rc_grow_mem] exact Or.inl ih lemma rc_fold (n : Nat) (edges : List (List Nat)) (root k : Nat) : (List.range k).foldl (fun seen _ => rcGrow n edges seen) [root] = rcIter n edges root k := by induction k with | zero => rfl | succ k ih => simp [List.range_succ, List.foldl_append, ih, rcIter] lemma rc_vertex_bound (n v : Nat) (hv : v ∈ vertexList n) : v < n+1 := by simp only [vertexList, List.mem_map, List.mem_range] at hv obtain ⟨k, hk, rfl⟩ := hv omega theorem reach_bridge (n : Nat) (edges : List (List Nat)) (root v : Nat) (bound : ∀ a b, [a,b] ∈ edges → b ∈ vertexList n) (hr : root ∈ vertexList n) (hv : v ∈ vertexList n) : v ∈ reachableFrom n edges root ↔ Relation.ReflTransGen (edgeDigraph edges).Adj root v := by change v ∈ (List.range (n+1)).foldl (fun seen _ => rcGrow n edges seen) [root] ↔ _ rw [rc_fold] constructor · exact rc_iter_sound n edges root (n+1) v · intro path obtain ⟨_, k, hk, hp⟩ := WxEconomy.wx_reachable_bounded_nat (n+1) (edgeDigraph edges).Adj (fun a b _ hab => rc_vertex_bound n b (bound a b hab)) (rc_vertex_bound n root hr) path exact rc_iter_mono n edges root k (n+1) v hk (rc_iter_complete n edges root bound k v hp) theorem root_with_reach (input : Input) (result : Output) (h : isValidInput input) (bridge : ∀ (input : Input), isValidInput input → (∀ (n : Nat) (edges : List (List Nat)) (root v : Nat), (∀ a b, [a,b] ∈ edges → b ∈ vertexList n) → root ∈ vertexList n → v ∈ vertexList n → (v ∈ reachableFrom n edges root ↔ Relation.ReflTransGen (edgeDigraph edges).Adj root v)) → ∀ e, isRemovableEdge input e ↔ IsRemovableEdge input e) : redundantConnection_check input result ↔ redundantConnection_spec input result := by exact root_of_bridges input result (bridge input h reach_bridge) lemma incomingCount_zero_iff (edges : List (List Nat)) (n v : Nat) (shape : ∀ x ∈ edges, ∃ a b, x = [a, b] ∧ a ∈ vertexList n) : incomingCount edges v = 0 ↔ ∀ u ∈ vertexList n, [u, v] ∉ edges := by unfold incomingCount rw [List.length_eq_zero_iff, List.filter_eq_nil_iff] constructor · intro hz u huV huv have hx := hz [u, v] huv simpa using hx · intro hz x hx obtain ⟨a, b, rfl, ha⟩ := shape x hx by_cases hb : b = v · subst b exact (hz a ha hx).elim · simp [hb] lemma vertex_mem_iff (n v : Nat) : v ∈ vertexList n ↔ 1 ≤ v ∧ v ≤ n := by simp only [vertexList, List.mem_map, List.mem_range] constructor · rintro ⟨k, hk, rfl⟩ omega · rintro ⟨h1, h2⟩ exact ⟨v - 1, by omega, by omega⟩ lemma incomingCount_one_iff (edges : List (List Nat)) (n v : Nat) (hnodup : edges.Nodup) (shape : ∀ x ∈ edges, ∃ a b, x = [a, b] ∧ a ∈ vertexList n) : incomingCount edges v = 1 ↔ ∃! u : Nat, u ∈ vertexList n ∧ (edgeDigraph edges).Adj u v := by let p : List Nat → Bool := fun x => match x with | [_, w] => w == v | _ => false have hp : (edges.filter p).Nodup := hnodup.filter _ unfold incomingCount change (edges.filter p).length = 1 ↔ _ rw [List.length_eq_one_iff] constructor · rintro ⟨x, hx⟩ have hxm : x ∈ edges.filter p := by simp [hx] have hxe : x ∈ edges := (List.mem_filter.mp hxm).1 obtain ⟨a, b, rfl, ha⟩ := shape x hxe have hb : b = v := by have := (List.mem_filter.mp hxm).2 simpa [p] using this subst b refine ⟨a, ⟨ha, hxe⟩, ?_⟩ intro y hy have hye := hy.2 change [y, v] ∈ edges at hye have hym : [y, v] ∈ edges.filter p := List.mem_filter.mpr ⟨hye, by simp [p]⟩ rw [hx] at hym simpa using hym · rintro ⟨u, ⟨huV, hue⟩, huniq⟩ change [u, v] ∈ edges at hue have hum : [u, v] ∈ edges.filter p := List.mem_filter.mpr ⟨hue, by simp [p]⟩ cases hf : edges.filter p with | nil => simp [hf] at hum | cons x xs => have hxmem : x ∈ edges.filter p := by simp [hf] have hxe : x ∈ edges := (List.mem_filter.mp hxmem).1 obtain ⟨a, b, rfl, ha⟩ := shape x hxe have hb : b = v := by have := (List.mem_filter.mp hxmem).2 simpa [p] using this subst b have hau : a = u := huniq a ⟨ha, hxe⟩ subst a have hxs : xs = [] := by apply List.eq_nil_iff_forall_not_mem.mpr intro z hz have hzm : z ∈ edges.filter p := by simp [hf, hz] have hze : z ∈ edges := (List.mem_filter.mp hzm).1 obtain ⟨c, d, rfl, hc⟩ := shape z hze have hd : d = v := by have := (List.mem_filter.mp hzm).2 simpa [p] using this subst d have hcu : c = u := huniq c ⟨hc, hze⟩ subst c exact (List.nodup_cons.mp (by simpa [hf] using hp)).1 hz simp [hf, hxs] lemma rootedTreeOn_iff (n : Nat) (edges : List (List Nat)) (hnodup : edges.Nodup) (shape : ∀ x ∈ edges, ∃ a b, x = [a, b] ∧ a ∈ vertexList n ∧ b ∈ vertexList n) (reach : ∀ (root v : Nat), root ∈ vertexList n → v ∈ vertexList n → (v ∈ reachableFrom n edges root ↔ Relation.ReflTransGen (edgeDigraph edges).Adj root v)) : isRootedTreeOn edges n ↔ IsRootedTree (edgeDigraph edges) n := by have hzero (v : Nat) : incomingCount edges v = 0 ↔ ∀ u ∈ vertexList n, ¬(edgeDigraph edges).Adj u v := by simpa [edgeDigraph] using incomingCount_zero_iff edges n v (fun x hx => let ⟨a, b, heq, ha, _⟩ := shape x hx ⟨a, b, heq, ha⟩) have hone (v : Nat) : incomingCount edges v = 1 ↔ ∃! u : Nat, u ∈ vertexList n ∧ (edgeDigraph edges).Adj u v := incomingCount_one_iff edges n v hnodup (fun x hx => let ⟨a, b, heq, ha, _⟩ := shape x hx ⟨a, b, heq, ha⟩) simp only [isRootedTreeOn, IsRootedTree, List.any_eq_true, List.all_eq_true, Bool.and_eq_true, Bool.or_eq_true, beq_iff_eq, List.contains_iff, hzero, hone] constructor · rintro ⟨root, hrV, ⟨hz, hones⟩, hrs⟩ refine ⟨root, hrV, ?_, hz, ?_⟩ · intro v hv exact (reach root v hrV hv).mp (hrs v hv) · intro v hv hne exact (hones v hv).resolve_left hne · rintro ⟨root, hrV, hrs, hz, hones⟩ refine ⟨root, hrV, ⟨hz, ?_⟩, ?_⟩ · intro v hv by_cases hvr : v = root · exact Or.inl hvr · exact Or.inr (hones v hv hvr) · intro v hv exact (reach root v hrV hv).mpr (hrs v hv) lemma removable_bridge : ∀ (input : Input), isValidInput input → (∀ (n : Nat) (edges : List (List Nat)) (root v : Nat), (∀ a b, [a,b] ∈ edges → b ∈ vertexList n) → root ∈ vertexList n → v ∈ vertexList n → (v ∈ reachableFrom n edges root ↔ Relation.ReflTransGen (edgeDigraph edges).Adj root v)) → ∀ e, isRemovableEdge input e ↔ IsRemovableEdge input e := by intro input hvalid reach e have hv := hvalid simp only [isValidInput, Bool.and_eq_true, List.all_eq_true, and_assoc] at hv obtain ⟨_, _, hedge, _, hcount, _⟩ := hv have hnodup : input.Nodup := List.nodup_iff_count_eq_one.mpr (by intro x hx have := hcount x hx simpa using this) have hshape : ∀ x ∈ input, ∃ a b, x = [a, b] ∧ a ∈ vertexList input.length ∧ b ∈ vertexList input.length := by intro x hx have hxv := hedge x hx split at hxv <;> simp_all [Bool.and_eq_true, decide_eq_true_eq, bne_iff_ne, vertex_mem_iff] have heraseNodup : (input.erase e).Nodup := hnodup.erase _ have heraseShape : ∀ x ∈ input.erase e, ∃ a b, x = [a, b] ∧ a ∈ vertexList input.length ∧ b ∈ vertexList input.length := by intro x hx exact hshape x (List.mem_of_mem_erase hx) have heraseReach (root v : Nat) (hr : root ∈ vertexList input.length) (hv : v ∈ vertexList input.length) : (v ∈ reachableFrom input.length (input.erase e) root ↔ Relation.ReflTransGen (edgeDigraph (input.erase e)).Adj root v) := by apply reach input.length (input.erase e) root v · intro a b hab obtain ⟨a', b', heq, _, hb⟩ := heraseShape [a, b] hab have hab' : a = a' ∧ b = b' := by simpa using heq simpa [hab'.2] using hb · exact hr · exact hv have hrooted := rootedTreeOn_iff input.length (input.erase e) heraseNodup heraseShape heraseReach have hadj (a b : Nat) : (edgeDigraph (input.erase e)).Adj a b ↔ (edgeDigraph input \ edgeDigraph [e]).Adj a b := by simp only [edgeDigraph, Digraph.sdiff_adj] simpa [hnodup.mem_erase_iff, and_comm, ne_eq] have hgraph : edgeDigraph (input.erase e) = edgeDigraph input \ edgeDigraph [e] := by apply Digraph.ext funext a b exact propext (hadj a b) simp only [isRemovableEdge, IsRemovableEdge, Bool.and_eq_true, List.contains_iff, hrooted, hgraph] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem redundantConnection_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : redundantConnection_check input result ↔ redundantConnection_spec input result := by exact root_with_reach input result h removable_bridge /-! ### Implementation helpers -/ /-- The two edges entering the first vertex of indegree 2, in input order, if any. -/ def twoParentConflict (edges : List (List Nat)) : Option (List Nat × List Nat) := let n := edges.length (vertexList n).findSome? (fun v => if incomingCount edges v == 2 then match edges.filter (fun e => match e with | [_, w] => w == v | _ => false) with | a :: b :: _ => some (a, b) | _ => none else none) /-- Bounded DSU root lookup: climbs parent pointers at most `n` times. -/ def findRoot (parent : Array Nat) (n x : Nat) : Nat := (List.range n).foldl (fun cur _ => parent[cur]!) x /-- Insert an edge into the DSU; `none` when its endpoints already share a root. -/ def tryUnion (parent : Array Nat) (n : Nat) (e : List Nat) : Option (Array Nat) := match e with | [u, v] => let ru := findRoot parent n u let rv := findRoot parent n v if ru == rv then none else some (parent.set! ru rv) | _ => some parent /-! ### Main algorithm (impl) -/ /-- Union-find over the edge list: with a two-parent vertex, drop its later parent edge unless that edge is needed to close the cycle; otherwise return the edge whose insertion closes the unique cycle. -/ def findRedundantDirectedConnection (input : Input) : Output := let n := input.length match twoParentConflict input with | some (a, b) => let merged := (input.erase b).foldl (fun acc e => acc.bind (fun parent => tryUnion parent n e)) (some (Array.range (n + 1))) match merged with | none => a | some _ => b | none => let scan := input.foldl (fun (acc : Array Nat × Option (List Nat)) e => match acc.2 with | some _ => acc | none => match tryUnion acc.1 n e with | some parent => (parent, none) | none => (acc.1, some e)) (Array.range (n + 1), none) scan.2.getD [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findRedundantDirectedConnection_correct (input : Input) (h : isValidInput input) : redundantConnection_spec input (findRedundantDirectedConnection input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 2], [1, 3], [2, 3]] #guard isValidInput [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] #guard isValidInput [[1, 2], [2, 3], [3, 1]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [[1, 2], [2, 1]]) #guard !(isValidInput [[1, 2], [2, 3], [1]]) #guard !(isValidInput [[1, 2], [2, 3], [0, 3]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard redundantConnection_check [[1, 2], [1, 3], [2, 3]] [2, 3] #guard redundantConnection_check [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] [4, 1] #guard redundantConnection_check [[1, 2], [2, 3], [3, 1]] [3, 1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(redundantConnection_check [[1, 2], [1, 3], [2, 3]] [1, 3]) #guard !(redundantConnection_check [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] [2, 3]) #guard !(redundantConnection_check [[1, 2], [2, 3], [3, 1]] [1, 2]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findRedundantDirectedConnection [[1, 2], [1, 3], [2, 3]] == [2, 3] #guard findRedundantDirectedConnection [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] == [4, 1] #guard findRedundantDirectedConnection [[1, 2], [2, 3], [3, 1]] == [3, 1] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard redundantConnection_check [[1, 2], [1, 3], [2, 3]] (findRedundantDirectedConnection [[1, 2], [1, 3], [2, 3]]) #guard redundantConnection_check [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]] (findRedundantDirectedConnection [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]) #guard redundantConnection_check [[1, 2], [2, 3], [3, 1]] (findRedundantDirectedConnection [[1, 2], [2, 3], [3, 1]]) end PRedundantConnectionIi