Problem

Given an undirected graph where each edge has a color (edge coloring), and two nodes s and d, count the number of distinct paths from s to d such that all edges in the path have the same color.

Input Format

  • n: Number of vertices (integer, 0-based indexing)
  • edges: List of edges, where each edge is represented as [u, v, color] (0-based)
  • s: Source node (integer)
  • d: Destination node (integer)

Examples

Example 1

graph TD
  A(1)
  B(0)
  2(2)
  3(3)
  4(4)
  
  B -- "1" --- A
  B -- "2" --- 2
  A -- "3" --- 2
  A -- "2" --- 3
  A -- "4" --- 4
  2 -- "3" --- 4
  3 -- "2" --- 4
  
  linkStyle 0 stroke:#d62728,stroke-width:3px; 
  linkStyle 1 stroke:#1f77b4,stroke-width:3px;
  linkStyle 2 stroke:#2ca02c,stroke-width:3px;
  linkStyle 3 stroke:#1f77b4,stroke-width:3px;
  linkStyle 4 stroke:#ff7f0e,stroke-width:3px;
  linkStyle 5 stroke:#2ca02c,stroke-width:3px;
  linkStyle 6 stroke:#1f77b4,stroke-width:3px;
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Input:
n = 6
edges = [
  [0, 1, 1],
  [0, 2, 2],
  [1, 2, 3],
  [1, 3, 2],
  [1, 4, 4],
  [2, 4, 3],
  [3, 4, 2]
]
s = 1
d = 4

Output: 3
Explanation: There are three unicolored paths from 1 to 4:
- 1 → 4 (color 4)
- 1 → 2 → 4 (color 3)
- 1 → 3 → 4 (color 2)

Solution

Method 1 – DFS for Each Color

Intuition

For each color, perform a DFS from the source, only traversing edges of that color, and count the number of ways to reach the destination.

Approach

  1. For each color present in the graph:
  • Do a DFS from the source to the destination, only following edges of that color.
  • Mark nodes as visited to avoid cycles.
  • If the destination is reached, increment the count for that color.
  1. Sum the counts for all colors.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
  int countUnicoloredPaths(const std::vector<std::tuple<int,int,int>>& edges, int n, int s, int d) {
    std::unordered_map<int, std::vector<std::pair<int,int>>> adj;
    std::unordered_set<int> colors;
    for (auto& [u, v, c] : edges) {
      adj[u].emplace_back(v, c);
      adj[v].emplace_back(u, c);
      colors.insert(c);
    }
    int ans = 0;
    for (int color : colors) {
      std::vector<bool> vis(n+1, false);
      ans += dfs(adj, s, d, color, vis);
    }
    return ans;
  }
private:
  int dfs(const std::unordered_map<int, std::vector<std::pair<int,int>>>& adj, int u, int d, int color, std::vector<bool>& vis) {
    if (u == d) return 1;
    vis[u] = true;
    int cnt = 0;
    for (auto& [v, c] : adj.at(u)) {
      if (!vis[v] && c == color) cnt += dfs(adj, v, d, color, vis);
    }
    vis[u] = false;
    return cnt;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
  public int countUnicoloredPaths(List<int[]> edges, int n, int s, int d) {
    Map<Integer, List<int[]>> adj = new HashMap<>();
    Set<Integer> colors = new HashSet<>();
    for (int[] e : edges) {
      adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(new int[]{e[1], e[2]});
      adj.computeIfAbsent(e[1], k -> new ArrayList<>()).add(new int[]{e[0], e[2]});
      colors.add(e[2]);
    }
    int ans = 0;
    for (int color : colors) {
      boolean[] vis = new boolean[n+1];
      ans += dfs(adj, s, d, color, vis);
    }
    return ans;
  }
  private int dfs(Map<Integer, List<int[]>> adj, int u, int d, int color, boolean[] vis) {
    if (u == d) return 1;
    vis[u] = true;
    int cnt = 0;
    for (int[] pair : adj.getOrDefault(u, new ArrayList<>())) {
      int v = pair[0], c = pair[1];
      if (!vis[v] && c == color) cnt += dfs(adj, v, d, color, vis);
    }
    vis[u] = false;
    return cnt;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
  def count_unicolored_paths(self, edges: list[tuple[int,int,int]], n: int, s: int, d: int) -> int:
    from collections import defaultdict
    adj = defaultdict(list)
    colors = set()
    for u, v, c in edges:
      adj[u].append((v, c))
      adj[v].append((u, c))
      colors.add(c)
    def dfs(u, color, vis):
      if u == d:
        return 1
      vis.add(u)
      cnt = 0
      for v, c in adj[u]:
        if v not in vis and c == color:
          cnt += dfs(v, color, vis)
      vis.remove(u)
      return cnt
    ans = 0
    for color in colors:
      ans += dfs(s, color, set())
    return ans

Complexity

  • ⏰ Time complexity: O(E * (E + V)), where E is the number of edges and V is the number of vertices. For each color, a DFS is performed.
  • 🧺 Space complexity: O(V + E), for adjacency lists and recursion stack.