個数の特定

Question

競技中に出席している質問がありますが、解決できませんでした。 質問：Nの頂点およびMエッジを有する無向グラフが与えられたとすると、

が与えられます。各辺は、{1,...C}の色のいずれかで色付けされています。 のクエリが整数のペアxとyの形式で存在します。特定のクエリについては、別の色の数が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,4,2}である5vertexの頂点5から唯一の経路、含有があります2つの異なる色、すなわち{3,2}。

この質問を解決するにはFull Problem Statement？ 制約：

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

Answer 1

色Cが場合uからvに各単純パス上に存在している場合のみ：uとvの間に経路が存在する

1. 。

2. Cのすべてのエッジが削除されたグラフでは、uとvの間にパスがありません。 （証明：この色のエッジがないグラフにパスがない場合、元のグラフのuからvまでの各パスには少なくとも1つのエッジが含まれています逆に、単純パスには特定の色のエッジが含まれている場合、その2つの頂点を明確に切り離す）。

この観察は、以下の溶液をもたらす：

1. は、（例えば、使用することにより、深さ優先探索）元のグラフにおける連結成分を探します。

2. 各色1 <= c <= Cについては、cの色のすべてのエッジを削除し、新しいグラフで接続されたコンポーネントを見つけます。

3. xとyが元のグラフで異なるコンポーネントにある場合、(x, y)クエリに対する答えがそうでなければ0である、そのような色の数に等しいだcxとyをなしグラフで異なるコンポーネントにあること色の端はcです。

時間複雑度は、（第1項はC + 1深さ優先検索に対応する。第1は、各クエリのすべての色上の反復に相当）O((N + M) * (C + 1) + Q * C)あります。