Paths in maze that lead to same room

Graph Theory

56.5% acceptance

Mar 31, 2026

143

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;

impl Solution {
  pub fn number_of_paths(n: i32, corridors: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj: Vec<HashSet<usize>> = vec![HashSet::new(); n + 1];
    for c in &corridors {
      let u = c[0] as usize;
      let v = c[1] as usize;
      adj[u].insert(v);
      adj[v].insert(u);
    }

    let mut count = 0;
    for c in &corridors {
      let u = c[0] as usize;
      let v = c[1] as usize;
      for &w in &adj[u] {
        if adj[v].contains(&w) {
          count += 1;
        }
      }
    }

    count / 3
  }
}