Replaced hand-rolled Kahn's algorithm with petgraph::Graph and
is_cyclic_directed/toposort. The reachability check stays as a manual
DFS because source refs (e.g. quire/push) are not graph nodes.

Assisted-by: GLM-5.1 via pi

diff --git a/Cargo.lock b/Cargo.lock
index 5c27fd3..b3dc9e4 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -681,6 +681,12 @@ dependencies = [
  "winapi",
 ]
 
+[[package]]
+name = "fixedbitset"
+version = "0.5.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1d674e81391d1e1ab681a28d99df07927c6d4aa5b027d7da16ba32d1d21ecd99"
+
 [[package]]
 name = "float-cmp"
 version = "0.10.0"
@@ -1748,6 +1754,18 @@ version = "2.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "9b4f627cb1b25917193a259e49bdad08f671f8d9708acfd5fe0a8c1455d87220"
 
+[[package]]
+name = "petgraph"
+version = "0.8.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8701b58ea97060d5e5b155d383a69952a60943f0e6dfe30b04c287beb0b27455"
+dependencies = [
+ "fixedbitset",
+ "hashbrown 0.15.5",
+ "indexmap",
+ "serde",
+]
+
 [[package]]
 name = "pin-project-lite"
 version = "0.2.17"
@@ -1917,6 +1935,7 @@ dependencies = [
  "jiff",
  "miette",
  "mlua",
+ "petgraph",
  "predicates",
  "regex",
  "sentry",
diff --git a/Cargo.toml b/Cargo.toml
index 668adee..f18361d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -17,6 +17,7 @@ jiff = "*"
 miette = { version = "*", features = ["fancy"] }
 mlua = { version = "*", features = ["lua54", "serde", "vendored", "error-send"] }
 regex = "*"
+petgraph = "*"
 sentry = { version = "*", features = ["backtrace", "contexts", "debug-images", "panic", "release-health", "reqwest", "rustls", "tokio"], default-features = false }
 sentry-tracing = "*"
 serde = { version = "*", features = ["derive"] }
diff --git a/src/ci.rs b/src/ci.rs
index 21c63e8..8af5705 100644
--- a/src/ci.rs
+++ b/src/ci.rs
@@ -373,9 +373,6 @@ pub enum ValidationError {
 pub fn validate(jobs: &[JobDef]) -> std::result::Result<(), Vec<ValidationError>> {
     let mut errors = Vec::new();
 
-    // Build a set of known job ids.
-    let job_ids: std::collections::HashSet<&str> = jobs.iter().map(|j| j.id.as_str()).collect();
-
     // Rule 4: no '/' in user job ids.
     for job in jobs {
         if job.id.contains('/') {
@@ -394,46 +391,34 @@ pub fn validate(jobs: &[JobDef]) -> std::result::Result<(), Vec<ValidationError>
         }
     }
 
-    // Rule 1: acyclic (Kahn's algorithm).
-    let mut in_degree: std::collections::HashMap<&str, usize> =
-        jobs.iter().map(|j| (j.id.as_str(), 0)).collect();
-    let mut adjacency: std::collections::HashMap<&str, Vec<&str>> =
-        jobs.iter().map(|j| (j.id.as_str(), Vec::new())).collect();
+    // Rule 1: acyclic.
+    //
+    // Build a directed graph where edges point from dependency to
+    // dependent. Source refs (e.g. "quire/push") are not nodes.
+    let mut graph: petgraph::Graph<&str, ()> = petgraph::Graph::new();
+    let mut node_map: std::collections::HashMap<&str, petgraph::graph::NodeIndex> =
+        std::collections::HashMap::new();
 
     for job in jobs {
-        for input in &job.inputs {
-            if job_ids.contains(input.as_str()) {
-                *in_degree.entry(job.id.as_str()).or_insert(0) += 1;
-                adjacency
-                    .entry(input.as_str())
-                    .or_default()
-                    .push(job.id.as_str());
-            }
-        }
+        let idx = graph.add_node(job.id.as_str());
+        node_map.insert(job.id.as_str(), idx);
     }
 
-    let mut queue: Vec<&str> = in_degree
-        .iter()
-        .filter(|&(_, &deg)| deg == 0)
-        .map(|(&id, _)| id)
-        .collect();
-    let mut sorted = Vec::new();
-
-    while let Some(id) = queue.pop() {
-        sorted.push(id);
-        if let Some(dependents) = adjacency.get(id) {
-            for &dep in dependents {
-                if let Some(deg) = in_degree.get_mut(dep) {
-                    *deg -= 1;
-                    if *deg == 0 {
-                        queue.push(dep);
-                    }
-                }
+    for job in jobs {
+        let dependent = node_map[job.id.as_str()];
+        for input in &job.inputs {
+            if let Some(&dependency) = node_map.get(input.as_str()) {
+                graph.add_edge(dependency, dependent, ());
             }
         }
     }
 
-    if sorted.len() != jobs.len() {
+    if petgraph::algo::is_cyclic_directed(&graph) {
+        let sorted: std::collections::HashSet<_> = petgraph::algo::toposort(&graph, None)
+            .unwrap_or_default()
+            .into_iter()
+            .map(|idx| graph[idx])
+            .collect();
         let cycle_jobs: Vec<String> = jobs
             .iter()
             .map(|j| j.id.as_str())