Question

2077. Paths in Maze That Lead to Same Room

中文文档

Description

A maze consists of n rooms numbered from 1 to n, and some rooms are connected by corridors. You are given a 2D integer array corridors where corridors[i] = [room1i, room2i] indicates that there is a corridor connecting room1i and room2i, allowing a person in the maze to go from room1i to room2i and vice versa.

The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.

• For example, 1 → 2 → 3 → 1 is a cycle of length 3, but 1 → 2 → 3 → 4 and 1 → 2 → 3 → 2 → 1 are not.

Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.

Return _the_ _confusion score of the maze._

 

Example 1:

Input: n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]
Output: 2
Explanation:
One cycle of length 3 is 4 → 1 → 3 → 4, denoted in red.
Note that this is the same cycle as 3 → 4 → 1 → 3 or 1 → 3 → 4 → 1 because the rooms are the same.
Another cycle of length 3 is 1 → 2 → 4 → 1, denoted in blue.
Thus, there are two different cycles of length 3.

Example 2:

Input: n = 4, corridors = [[1,2],[3,4]]
Output: 0
Explanation:
There are no cycles of length 3.

 

Constraints:

• 2 <= n <= 1000
• 1 <= corridors.length <= 5 * 104
• corridors[i].length == 2
• 1 <= room1i, room2i <= n
• room1i != room2i
• There are no duplicate corridors.

Solutions

Solution 1

class Solution:
  def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
    g = defaultdict(set)
    for a, b in corridors:
      g[a].add(b)
      g[b].add(a)
    ans = 0
    for i in range(1, n + 1):
      for j, k in combinations(g[i], 2):
        if j in g[k]:
          ans += 1
    return ans // 3

class Solution {
  public int numberOfPaths(int n, int[][] corridors) {
    Set<Integer>[] g = new Set[n + 1];
    for (int i = 0; i <= n; ++i) {
      g[i] = new HashSet<>();
    }
    for (var c : corridors) {
      int a = c[0], b = c[1];
      g[a].add(b);
      g[b].add(a);
    }
    int ans = 0;
    for (int c = 1; c <= n; ++c) {
      var nxt = new ArrayList<>(g[c]);
      int m = nxt.size();
      for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
          int a = nxt.get(i), b = nxt.get(j);
          if (g[b].contains(a)) {
            ++ans;
          }
        }
      }
    }
    return ans / 3;
  }
}

class Solution {
public:
  int numberOfPaths(int n, vector<vector<int>>& corridors) {
    vector<unordered_set<int>> g(n + 1);
    for (auto& c : corridors) {
      int a = c[0], b = c[1];
      g[a].insert(b);
      g[b].insert(a);
    }
    int ans = 0;
    for (int c = 1; c <= n; ++c) {
      vector<int> nxt;
      nxt.assign(g[c].begin(), g[c].end());
      int m = nxt.size();
      for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
          int a = nxt[i], b = nxt[j];
          ans += g[b].count(a);
        }
      }
    }
    return ans / 3;
  }
};

func numberOfPaths(n int, corridors [][]int) int {
  g := make([]map[int]bool, n+1)
  for i := range g {
    g[i] = make(map[int]bool)
  }
  for _, c := range corridors {
    a, b := c[0], c[1]
    g[a][b] = true
    g[b][a] = true
  }
  ans := 0
  for c := 1; c <= n; c++ {
    nxt := []int{}
    for v := range g[c] {
      nxt = append(nxt, v)
    }
    m := len(nxt)
    for i := 0; i < m; i++ {
      for j := i + 1; j < m; j++ {
        a, b := nxt[i], nxt[j]
        if g[b][a] {
          ans++
        }
      }
    }
  }
  return ans / 3
}