找到不同顏色的號碼

Question

有問題，我參加了比賽，但我無法解決它。 問題：

給定一個無向圖，其頂點和M邊有N。每個邊緣都由來自集合{1,...C}的一種顏色着色。有一對x和y形式的q查詢。對於給定的查詢，找到present on each simple path from vertex to vertex不同顏色的數量。

輸入：

5 4 4 // N,M,C 
1 2 2 // U and V Nodes have Colour C 
1 3 1 
2 4 2 
4 5 3 
5  // Q 
4 1 // X,Y 
5 4 
5 2 
2 3 
5 4 

輸出：

1 
1 
2 
2 
1 

對於第三查詢，僅存在一個從頂點5至5vertex {5,4,2}的路徑，這是，它包含兩種不同的顏色，即{3,2}。

如何解決這個問題Full Problem Statement？ 約束：

1<C<40 
N and M are in order 10^5 

Answer 1

彩色C存在從u到v每個簡單的路徑上，當且僅當：

1. 有u和v之間的路徑。

2. 在圖中的u和v之間沒有路徑，其中顏色C的所有邊緣都被移除。 （證明：如果圖中沒有沒有這種顏色的邊的路徑，原始圖中從u到v的每條路徑至少包含一個這種顏色的邊，反之，如果每條簡單路徑都包含特定顏色的邊，它的移除將清楚地斷開這兩個頂點）。

這個觀察導致下面的解決方案：

1. 查找原始圖連接的組件（通過使用，例如，深度優先搜索）。

2. 對於每種顏色1 <= c <= C，刪除顏色c的所有邊，並在新圖中找到連接的組件。

3. 如果x和y是在原始圖不同的組件，回答一個(x, y)查詢是0。否則，它是等於這些顏色的數量c該x和y是在沒有圖中的不同組件顏色的邊緣c。

時間複雜度爲O((N + M) * (C + 1) + Q * C)（第一項對應於C + 1深度優先搜索。第二個對應於所述迭代在所有的顏色爲每個查詢）。