Cod sursa(job #3374174)

Utilizator mateivoican2006@gmail.comVoican Matei [email protected] Data 8 noiembrie 2026 19:57:41
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.93 kb
def main():
    d = open("easygraph.in", "rb").read().split()
    p = 0
    T = int(d[p]); p += 1
    out = []
    for _ in range(T):
        n, m = int(d[p]), int(d[p + 1]); p += 2
        best = [0] + [int(x) for x in d[p:p + n]]; p += n
        g = [[] for _ in range(n + 1)]
        intra = [0] * (n + 1)
        for _ in range(m):
            x, y = int(d[p]), int(d[p + 1]); p += 2
            g[x].append(y)
            intra[y] += 1

        val = best[:]
        coada = [i for i in range(1, n + 1) if intra[i] == 0]
        for v in coada:
            if best[v] > 0:
                for u in g[v]:
                    if best[v] + val[u] > best[u]:
                        best[u] = best[v] + val[u]
            for u in g[v]:
                intra[u] -= 1
                if intra[u] == 0:
                    coada.append(u)
        out.append(max(best[1:]))
    open("easygraph.out", "w").write("\n".join(map(str, out)) + "\n")

main()