import Mathlib /-! # Redundant Connection In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input. ## Constraints - n == edges.length - 3 <= n <= 1000 - edges[i].length == 2 - 1 <= a_i < b_i <= edges.length - a_i != b_i - There are no repeated edges. - The given graph is connected. ## Provided examples - `edges = [[1, 2], [1, 3], [2, 3]]` → `[2, 3]` - `edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]` → `[1, 4]` - `edges = [[1, 2], [2, 3], [3, 4], [2, 4]]` → `[2, 4]` ## Synthesized negative examples - invalid input: `edges = []` ([structural] a predicate that admits 3 <= n <= 1000. empty input below the 3-node minimum) - invalid input: `edges = [[1, 2], [2, 3], [1, 2, 3]]` ([structural] a predicate that admits edges[i].length == 2. edge tuple has three entries; predicate reading first two entries accepts it) - invalid input: `edges = [[0, 1], [1, 2], [2, 3]]` ([structural] a predicate that admits 1 <= ai < bi <= edges.length. endpoint 0 is outside the 1..n label set) - `edges = [[1, 2], [1, 3], [2, 3]]` → `[1, 2]` is wrong ([structural] specification lost the last-in-input tightness clause; accepts any valid removal. valid removal but not the last such edge) - `edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]` → `[2, 3]` is wrong ([structural] any removable edge accepted; latest-edge requirement dropped. Removing [2,3] leaves a tree but [1,4] is later.) - `edges = [[1, 2], [2, 3], [3, 4], [2, 4]]` → `[2, 3]` is wrong ([structural] any valid removable edge is accepted; the last-in-input condition is dropped. 删 [2,3] 也能得到树, 但输入里最后成环的是 [2,4]) -/ namespace PRedundantConnection abbrev Input := List (List Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- Index of the first occurrence of `a` in `l`, equal to `l.length` when `a` is absent. -/ def List.indexOf {α : Type} [BEq α] (l : List α) (a : α) : Nat := l.findIdx (· == a) /-- The simple graph on vertices `1, …, n` represented as `Fin n`, adjacent when the edge list contains the pair. -/ def edgeGraph (n : Nat) (edges : List (List Nat)) : SimpleGraph (Fin n) where Adj i j := i ≠ j ∧ ([i.val + 1, j.val + 1] ∈ edges ∨ [j.val + 1, i.val + 1] ∈ edges) symm := by constructor intro i j h exact ⟨h.1.symm, h.2.symm⟩ loopless := by constructor intro a h exact h.1 rfl /-- Adjacency in `edgeGraph` is decidable, being list membership on a finite list. -/ instance instDecidableRelEdgeGraphAdj (n : Nat) (edges : List (List Nat)) : DecidableRel (edgeGraph n edges).Adj := fun i j => inferInstanceAs (Decidable (i ≠ j ∧ ([i.val + 1, j.val + 1] ∈ edges ∨ [j.val + 1, i.val + 1] ∈ edges))) /-- The graph on vertices `1..edges.length` with `removed` erased from the edge set is a tree. -/ def IsTreeAfterRemovingEdge (edges : List (List Nat)) (removed : List Nat) : Prop := (edgeGraph edges.length (edges.erase removed)).IsTree /-- A well-formed edge entry: exactly two endpoints `a b` with `1 ≤ a < b ≤ n`. -/ def edgeCheck (n : Nat) (e : List Nat) : Bool := match e with | [a, b] => decide (1 ≤ a ∧ a < b ∧ b ≤ n) | _ => false /-! ### Validity predicate (V) -/ /-- Valid input: `n = edges.length` in `3..1000`, well-formed unrepeated edges, and a connected unicyclic graph. -/ def isValidInput (edges : Input) : Bool := let n := edges.length decide (3 ≤ n ∧ n ≤ 1000) && edges.all (edgeCheck n) && edges.all (fun e => decide (edges.count e = 1)) && decide (edgeGraph n edges).Connected && edges.any (fun e => decide (edgeGraph n (edges.erase e)).Connected) /-! ### Ideal specification (P_spec) -/ /-- `result` is an input edge whose removal leaves a tree, and no edge occurring later in the input is. -/ def redundantConnection_spec (input : Input) (result : Output) : Prop := (result ∈ input ∧ IsTreeAfterRemovingEdge input result) ∧ ∀ e ∈ input, input.findIdx (· == result) < input.findIdx (· == e) → ¬ IsTreeAfterRemovingEdge input e /-! ### Decidable specification (P_check) -/ /-- Connectedness stand-in for `IsTreeAfterRemovingEdge`: after erasing a listed edge the valid graph has `n` vertices and `n − 1` edges, where connected and tree agree. -/ abbrev removalLeavesTree (input : Input) (removed : List Nat) : Prop := (edgeGraph input.length (input.erase removed)).Connected /-- Executable checker for `redundantConnection_spec`, with `removalLeavesTree` in place of the tree predicate. -/ def redundantConnection_check (input : Input) (result : Output) : Bool := decide ((result ∈ input ∧ removalLeavesTree input result) ∧ ∀ e ∈ input, input.findIdx (· == result) < input.findIdx (· == e) → ¬ removalLeavesTree input e) theorem redundantConnection_edges_wf (input : Input) (h : isValidInput input) : ∀ e ∈ input, ∃ a b, e = [a, b] ∧ a < b := by have h' : input.all (edgeCheck input.length) = true := by simp only [isValidInput, Bool.and_eq_true] at h tauto rw [List.all_eq_true] at h' intro e he have hc := h' e he match e, hc with | [a, b], hc => simp only [edgeCheck, decide_eq_true_eq] at hc exact ⟨a, b, rfl, hc.2.1⟩ theorem redundantConnection_canon_mem (n : Nat) (L : List (List Nat)) (hL : ∀ e ∈ L, ∃ a b, e = [a, b] ∧ a < b) {i j : Fin n} (hij : (edgeGraph n L).Adj i j) : [min i.val j.val + 1, max i.val j.val + 1] ∈ L := by obtain ⟨hne, hin | hin⟩ := hij · obtain ⟨a, b, hab, hlt⟩ := hL _ hin have h1 : i.val + 1 = a ∧ j.val + 1 = b := by simpa using hab have hm : min i.val j.val = i.val := by omega have hM : max i.val j.val = j.val := by omega rw [hm, hM]; exact hin · obtain ⟨a, b, hab, hlt⟩ := hL _ hin have h1 : j.val + 1 = a ∧ i.val + 1 = b := by simpa using hab have hm : min i.val j.val = j.val := by omega have hM : max i.val j.val = i.val := by omega rw [hm, hM]; exact hin theorem redundantConnection_card_edgeSet_le (n : Nat) (L : List (List Nat)) (hL : ∀ e ∈ L, ∃ a b, e = [a, b] ∧ a < b) : Nat.card (edgeGraph n L).edgeSet ≤ L.length := by have hcard : Nat.card (edgeGraph n L).edgeSet = (edgeGraph n L).edgeFinset.card := by rw [SimpleGraph.edgeFinset_card, Nat.card_eq_fintype_card] rw [hcard] refine le_trans (Finset.card_le_card_of_injOn (Sym2.lift ⟨fun i j => [min i.val j.val + 1, max i.val j.val + 1], fun a b => by dsimp only rw [Nat.min_comm, Nat.max_comm]⟩) ?_ ?_) (List.toFinset_card_le L) · intro x hx induction x using Sym2.ind with | h i j => rw [Finset.mem_coe, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at hx simp only [Sym2.lift_mk, Finset.mem_coe, List.mem_toFinset] exact redundantConnection_canon_mem n L hL hx · intro x hx y hy hxy induction x using Sym2.ind with | h i j => induction y using Sym2.ind with | h k l => simp only [Sym2.lift_mk, List.cons.injEq, and_true] at hxy obtain ⟨e1, e2⟩ := hxy rw [Sym2.eq_iff] have h1 : (i.val = k.val ∧ j.val = l.val) ∨ (i.val = l.val ∧ j.val = k.val) := by omega rcases h1 with ⟨p, q⟩ | ⟨p, q⟩ · exact Or.inl ⟨Fin.ext p, Fin.ext q⟩ · exact Or.inr ⟨Fin.ext p, Fin.ext q⟩ theorem redundantConnection_removal_iff (input : Input) (h : isValidInput input) (e : List Nat) (he : e ∈ input) : removalLeavesTree input e ↔ IsTreeAfterRemovingEdge input e := by unfold removalLeavesTree IsTreeAfterRemovingEdge have hwf : ∀ x ∈ input.erase e, ∃ a b, x = [a, b] ∧ a < b := fun x hx => redundantConnection_edges_wf input h x (List.mem_of_mem_erase hx) have hlen : (input.erase e).length + 1 = input.length := by rw [List.length_erase_of_mem he] have hp : 0 < input.length := List.length_pos_of_mem he omega have hV : Nat.card (Fin input.length) = input.length := by rw [Nat.card_eq_fintype_card, Fintype.card_fin] constructor · intro hconn refine SimpleGraph.isTree_iff_connected_and_card.mpr ⟨hconn, ?_⟩ have hle := redundantConnection_card_edgeSet_le input.length (input.erase e) hwf have hge := hconn.card_vert_le_card_edgeSet_add_one rw [hV] at hge omega · intro htree exact (SimpleGraph.isTree_iff_connected_and_card.mp htree).1 /-- 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 simp only [redundantConnection_check, redundantConnection_spec, decide_eq_true_eq] constructor · rintro ⟨⟨hmem, hc⟩, h2⟩ exact ⟨⟨hmem, (redundantConnection_removal_iff input h result hmem).mp hc⟩, fun e he hlt hct => h2 e he hlt ((redundantConnection_removal_iff input h e he).mpr hct)⟩ · rintro ⟨⟨hmem, hc⟩, h2⟩ exact ⟨⟨hmem, (redundantConnection_removal_iff input h result hmem).mpr hc⟩, fun e he hlt hct => h2 e he hlt ((redundantConnection_removal_iff input h e he).mp hct)⟩ /-! ### Implementation helpers -/ /-- Fresh disjoint-set state over labels `0 .. n`: each vertex is its own representative, alone in a component of size one. -/ def initUnionFind (n : Nat) : Array Nat × Array Nat × Array (List Nat) := (Array.ofFn (fun i : Fin (n + 1) => i.val), Array.replicate (n + 1) 1, Array.ofFn (fun i : Fin (n + 1) => [i.val])) /-- Unites the components of `a` and `b` by moving the smaller member list onto the larger component's representative; returns the new state and whether the two were already connected. -/ def unionNodes (repr sizes : Array Nat) (members : Array (List Nat)) (a b : Nat) : Array Nat × Array Nat × Array (List Nat) × Bool := let ra := repr[a]! let rb := repr[b]! if ra = rb then (repr, sizes, members, false) else let (big, small) := if sizes[ra]! < sizes[rb]! then (rb, ra) else (ra, rb) let repr := (members[small]!).foldl (fun r v => r.set! v big) repr let sizes := (sizes.set! big (sizes[big]! + sizes[small]!)).set! small 0 let members := (members.set! big (members[big]! ++ members[small]!)).set! small [] (repr, sizes, members, true) /-- Folds the edge list in input order, uniting each pair and keeping the first edge whose endpoints already share a representative. -/ def processEdges (edges : List (List Nat)) (repr sizes : Array Nat) (members : Array (List Nat)) (answer : List Nat) : List Nat := match edges with | [] => answer | e :: rest => match e with | [a, b] => let (repr, sizes, members, united) := unionNodes repr sizes members a b processEdges rest repr sizes members (if united then answer else e) | _ => processEdges rest repr sizes members answer /-! ### Main algorithm (impl) -/ /-- Disjoint-set union over the edges in input order; the first edge whose endpoints already lie in one component closes the unique cycle. -/ def findRedundantConnection (edges : Input) : Output := let (repr, sizes, members) := initUnionFind edges.length processEdges edges repr sizes members [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findRedundantConnection_correct (input : Input) (h : isValidInput input) : redundantConnection_spec input (findRedundantConnection 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], [1, 4], [1, 5]] #guard isValidInput [[1, 2], [2, 3], [3, 4], [2, 4]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[1, 2], [2, 3], [1, 2, 3]]) #guard !(isValidInput [[0, 1], [1, 2], [2, 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], [1, 4], [1, 5]] [1, 4] #guard redundantConnection_check [[1, 2], [2, 3], [3, 4], [2, 4]] [2, 4] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(redundantConnection_check [[1, 2], [1, 3], [2, 3]] [1, 2]) #guard !(redundantConnection_check [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] [2, 3]) #guard !(redundantConnection_check [[1, 2], [2, 3], [3, 4], [2, 4]] [2, 3]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findRedundantConnection [[1, 2], [1, 3], [2, 3]] == [2, 3] #guard findRedundantConnection [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] == [1, 4] #guard findRedundantConnection [[1, 2], [2, 3], [3, 4], [2, 4]] == [2, 4] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard redundantConnection_check [[1, 2], [1, 3], [2, 3]] (findRedundantConnection [[1, 2], [1, 3], [2, 3]]) #guard redundantConnection_check [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] (findRedundantConnection [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) #guard redundantConnection_check [[1, 2], [2, 3], [3, 4], [2, 4]] (findRedundantConnection [[1, 2], [2, 3], [3, 4], [2, 4]]) end PRedundantConnection