找到不同颜色的数量

Question

我在比赛期间参加了一个问题,但我无法解决.问题:

给定具有N顶点和M边的无向图.每个边缘都用一组颜色着色{1,...C}.有q一对整数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到5vertex只有一条路径,即{5,4,2},它包含两种不同的颜色,即{3,2}.

如何解决这个问题完整的问题陈述？限制:

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深度优先搜索.第二项对应于每个查询的所有颜色的迭代).