1 files changed, 126 insertions, 11 deletions

diff --git a/src/main.rs b/src/main.rs
index c8865fa..5d0f49b 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -4,7 +4,7 @@ use std::time::Instant;
 
 struct Graph {
     size: usize,
-    matrix: Vec<Vec<u8>>,
+    matrix: Vec<Vec<u32>>,
 }
 
 impl Clone for Graph {
@@ -49,11 +49,11 @@ impl Graph {
         let size = chars[0] as usize;
         let bytes = &chars[1..];
 
-        let mut matrix: Vec<Vec<u8>> = vec![vec![0; size]; size];
+        let mut matrix: Vec<Vec<u32>> = vec![vec![0; size]; size];
         let mut i = 0;
         for col in 1..size {
             for row in 0..col {
-                let bit: u8 = bytes[i / 6] >> (5 - i % 6) & 1;
+                let bit: u32 = (bytes[i / 6] >> (5 - i % 6) & 1) as u32;
                 matrix[row][col] = bit;
                 matrix[col][row] = bit;
                 i += 1;
@@ -65,33 +65,127 @@ impl Graph {
     fn degree(&self, vertex: usize) -> usize {
         let mut sum: usize = 0;
         for i in &self.matrix[vertex] {
-            sum += *i as usize;
+            sum += if *i == 0 { 0 } else { 1 } as usize;
         }
         return sum;
     }
 
-    fn get_closure(&self) -> Graph {
+    fn get_closure_traced(&self, trace_steps: bool) -> Graph {
+        let mut step = if trace_steps { 2 } else { 1 };
+
         let mut closure = self.clone();
         for _ in 0..(closure.size * closure.size) {
+            let mut changed = false;
             for row in 0..closure.size {
                 for col in 0..closure.size {
-                    if row == col {
+                    if row == col || closure.matrix[row][col] != 0 {
                         continue;
                     }
                     let sum = closure.degree(row) + closure.degree(col);
                     if sum >= closure.size {
-                        closure.matrix[row][col] = 1;
+                        closure.matrix[row][col] = step;
+                        if trace_steps {
+                            step += 1;
+                        }
+                        changed = true;
                     }
                 }
             }
+            if !changed {
+                break;
+            }
         }
         return closure;
     }
 
+    fn get_hamiltonian_cycle(&self) -> Vec<usize> {
+        let closure = self.get_closure_traced(true);
+
+        let mut cycle = Vec::new();
+        for i in 0..self.size - 1 {
+            cycle.push(i + 1);
+        }
+        cycle.push(0);
+
+        loop {
+            let mut start = 0;
+            let mut m = 0;
+
+            let mut end = start;
+            let mut new_start = start;
+            let mut current = start;
+            loop {
+                let next = cycle[current];
+                let val = closure.matrix[current][next];
+                // println!("{current} -> {next} = {val}");
+                if val > m {
+                    m = val;
+                    end = current;
+                    new_start = next;
+                }
+                current = next;
+                if current == start {
+                    break;
+                }
+            }
+            if m == 1 {
+                break;
+            }
+            // println!("New start: {new_start}, end: {end}, m = {m}");
+            start = new_start;
+
+            let mut s = start;
+            let mut current = cycle[start];
+            while current != end {
+                let next = cycle[current];
+                let u1 = closure.matrix[start][next];
+                let u2 = closure.matrix[end][current];
+                if u1 < m && u2 < m {
+                    s = current;
+                    break;
+                }
+                current = next;
+            }
+            // println!("s = {s}");
+
+            let mut new_cycle = Vec::new();
+            new_cycle.push(start);
+            let mut current = cycle[s];
+            while current != end {
+                new_cycle.push(current);
+                current = cycle[current];
+            }
+            new_cycle.push(end);
+            {
+                let mut tmp = Vec::new();
+                let mut current = cycle[start];
+                while current != s {
+                    tmp.push(current);
+                    current = cycle[current];
+                }
+                tmp.push(s);
+                tmp.reverse();
+                for i in tmp {
+                    new_cycle.push(i);
+                }
+            }
+            for i in 0..self.size - 1 {
+                cycle[new_cycle[i]] = new_cycle[i + 1];
+            }
+            cycle[new_cycle[self.size - 1]] = new_cycle[0];
+        }
+
+        return cycle;
+    }
+
+    fn get_closure(&self) -> Graph {
+        self.get_closure_traced(false)
+    }
+
     fn is_complete(&self) -> bool {
         for row in 0..self.size {
             for col in 0..self.size {
-                if row != col && self.matrix[row][col] != 1 {
+                if row != col && self.matrix[row][col] == 0 {
                     return false;
                 }
             }
@@ -108,16 +202,37 @@ fn main() {
     for line in stdin.lock().lines() {
         let line = line.unwrap();
 
-        let start = Instant::now();
         let g = Graph::from_g6(&line);
+
+        let start = Instant::now();
         let closure = g.get_closure();
-        if closure.is_complete() {
+        let is_complete = closure.is_complete();
+
+        if is_complete {
             count += 1;
         }
+
+        if is_complete {
+            println!("Graph: {line}\n{g}");
+            let cycle = g.get_hamiltonian_cycle();
+            print!("Cycle: ");
+            let start = 0;
+            let mut current = start;
+            loop {
+                print!("{}", current + 1);
+                print!(" -> ");
+                current = cycle[current];
+                if current == start {
+                    println!("{}", current + 1);
+                    break;
+                }
+            }
+        }
+
         let elapsed = start.elapsed();
         t += elapsed.as_nanos();
     }
 
-    println!("Time elapsed: {}s", t as f64 / 1e9);
     println!("Count of Hamiltonian graphs: {}", count);
+    println!("Time elapsed: {}s", t as f64 / 1e9);
 }