Description

Every house in the colony has at most one pipe going into it and at most one pipe going out of it. Tanks and taps are to be installed in a manner such that every house with one outgoing pipe but no incoming pipe gets a tank installed on its roof and every house with only an incoming pipe and no outgoing pipe gets a tap. Find the efficient way for the construction of the network of pipes.

Input

The first line contains an integer T denoting the number of test cases. For each test case, the first line contains two integer n & p denoting the number of houses and number of pipes respectively. Next, p lines contain 3 integer inputs a, b & d, d denoting the diameter of the pipe from the house a to house b.Constraints:1<=T<=50，1<=n<=20，1<=p<=50，1<=a, b<=20，1<=d<=100

Output

For each test case, the output is the number of pairs of tanks and taps installed i.e n followed by n lines that contain three integers: house number of tank, house number of tap and the minimum diameter of pipe between them.

Sample Input 1

1
9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66

Sample Output 1

3
2 8 22
3 1 66
5 6 10

思路

題目不好理解，畫個(gè)圖就好明白了

把上面的輸入輸出用例畫出來就是水管的連接圖，箭頭連接的是不同的人家，箭頭上面的數(shù)字是水管的直徑，我們需要在沒有輸入水管的人家安裝tank，在沒有輸出的人家安裝tap，所以需要安裝的是5 -> 6, 2 -> 8, 3 -> 1，至于安裝在它們之間的最小水管大小，就是連通路徑上的最小水管直徑。比如5 -> 6連通路徑上最小的直徑是10，因此最后結(jié)果就是10。

解題思路：

1. 找到所有的起點(diǎn)（5， 2， 3）

   可以先記錄所有路徑的起點(diǎn)，和終點(diǎn)，最后用起點(diǎn)減去終點(diǎn)，就能找到所有真實(shí)的起點(diǎn)。

2. 從起點(diǎn)開始，找出下一條路徑，直到?jīng)]有下一條路徑結(jié)束，記錄結(jié)束的點(diǎn)（與上面對(duì)應(yīng)的是6， 8， 1）

   記錄從起點(diǎn)到終點(diǎn)的路徑中，需要記錄管道直徑的最小值，最后輸出

python O(N)

def solve(p, pairs):
    link, vals = {}, {}
    for pair in pairs:
        link[pair[0]] = pair[1]
        vals[(pair[0], pair[1])] = pair[2]
    starts = set(link.keys()) - set(link.values())

    ans = []
    for s in starts:
        e = link[s]
        val = vals[(s, e)]
        while e in link:
            val = min(val, vals[e, link[e]])
            e = link[e]
        ans.append((s, e, val))

    return sorted(ans)


for _ in range(int(input())):
    p, t = map(int, input().strip().split())
    pairs = [tuple(map(int, input().strip().split())) for _ in range(t)]
    res = solve(p, pairs)
    print(len(res))
    for ans in res:
        print(*ans)