Mr. Kitayuta's Colorful Graph (Codeforces 505B)
Tags: DP, dsu

Mr. Kitayuta has just bought an undirected graph consisting of n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color ci, connecting vertex ai and bi.Mr. Kitayuta wants you to process the following q queries.In the i-th query, he gives you two integers — ui and vi.Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.

Input: The first line of the input contains space-separated two integers — n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100), denoting the number of the vertices and the number of the edges, respectively.The next m lines contain space-separated three integers — ai, bi (1 ≤ ai < bi ≤ n) and ci (1 ≤ ci ≤ m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i ≠ j, (ai, bi, ci) ≠ (aj, bj, cj).The next line contains a integer — q (1 ≤ q ≤ 100), denoting the number of the queries.Then follows q lines, containing space-separated two integers — ui and vi (1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.

Output: For each query, print the answer in a separate line.

Note: Let's consider the first sample.     The figure above shows the first sample.    Vertex 1 and vertex 2 are connected by color 1 and 2.  Vertex 3 and vertex 4 are connected by color 3.  Vertex 1 and vertex 4 are not connected by any single color. 

Sample Inputs:
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4

5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4

Sample Outputs:
2
1
0

1
1
1
1
2

Solution (Python):
from collections import defaultdict

def dfs(s, e, c, v, sw):
    ans = sw
    w = s
    v.append(w)
    if e in c[w]:
        return 1
    for i in c[w]:
        if i not in v:
            ans = dfs(i, e, c, v, ans)
    return ans
(n, m) = map(int, input().split())
num_list = [defaultdict(list) for i in range(m + 1)]
for i in range(m):
    (a, b, k) = map(int, input().split())
    num_list[k][a].append(b)
    num_list[k][b].append(a)
q = int(input())
for i in range(q):
    ans = 0
    c = tuple(map(int, input().split()))
    for j in num_list:
        if j:
            ans += dfs(c[0], c[1], j, [], 0)
    print(ans)

Solution (Python):
def frente(a, c):
    if f[c][a] != a:
        f[c][a] = frente(f[c][a], c)
    return f[c][a]

def antes(a, b, c):
    (ra, rb) = (frente(a, c), frente(b, c))
    if ra == rb:
        return
    f[c][ra] = rb
(n, m) = map(int, input().split())
f = [list(range(n + 1)) for _ in range(m + 2)]
for (a, b, c) in [map(int, input().split()) for _ in range(m)]:
    antes(a, b, c)
q = int(input())
for (x, y) in [map(int, input().split()) for _ in range(q)]:
    print(sum((1 for i in range(1, m + 1) if frente(x, i) == frente(y, i))))

Solution (Python):
def find(c, x):
    p = dsu[c]
    if x == p[x]:
        return x
    return find(c, p[x])

def union(c, x, y):
    x = find(c, x)
    y = find(c, y)
    if x == y:
        return
    p = dsu[c]
    p[x] = y
(n, m) = map(int, input().split())
dsu = [[i for i in range(n + 1)] for _ in range(m + 1)]
for _ in range(m):
    (a, b, c) = map(int, input().split())
    union(c, a, b)
q = int(input())
for _ in range(q):
    (a, b) = map(int, input().split())
    count = 0
    for c in range(1, m + 1):
        if find(c, a) == find(c, b):
            count += 1
    print(count)