Transitive Graph (Codeforces 1900E)
Tags: Implement, dsu

You are given a directed graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges between them.Initially, graph $$$H$$$ is the same as graph $$$G$$$. Then you decided to perform the following actions:   If there exists a triple of vertices $$$a$$$, $$$b$$$, $$$c$$$ of $$$H$$$, such that there is an edge from $$$a$$$ to $$$b$$$ and an edge from $$$b$$$ to $$$c$$$, but there is no edge from $$$a$$$ to $$$c$$$, add an edge from $$$a$$$ to $$$c$$$.  Repeat the previous step as long as there are such triples. Note that the number of edges in $$$H$$$ can be up to $$$n^2$$$ after performing the actions.You also wrote some values on vertices of graph $$$H$$$. More precisely, vertex $$$i$$$ has the value of $$$a_i$$$ written on it.Consider a simple path consisting of $$$k$$$ distinct vertices with indexes $$$v_1, v_2, \ldots, v_k$$$. The length of such a path is $$$k$$$. The value of that path is defined as $$$\sum_{i = 1}^k a_{v_i}$$$.A simple path is considered the longest if there is no other simple path in the graph with greater length.Among all the longest simple paths in $$$H$$$, find the one with the smallest value.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers written on the vertices of graph $$$H$$$.The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — meaning that there is an edge going from vertex $$$v_i$$$ to vertex $$$u_i$$$ in graph $$$G$$$. Note that edges are directed. Also note that the graph may have self-loops and multiple edges.It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases exceeds $$$2 \cdot 10^5$$$.

Output: For each test case, output two numbers — the length of the longest simple path in $$$H$$$ and the minimal possible value of such path.

Note: In the first test case, the longest path in both graphs is $$$1 \to 3 \to 4 \to 5 \to 2$$$. As the path includes all vertices, the minimal possible value of the longest path is the sum of values on all vertices, which is $$$12$$$.In the second test case, the longest possible path is $$$1 \to 2 \to 3 \to 4 \to 6 \to 7$$$. As there are no longest paths with vertex $$$5$$$ in them, this path has the minimal possible value of $$$5\,999\,999\,995$$$.In the third test case, it can be proven that there is no path longer than $$$11$$$ and that the value of the longest path cannot be less than $$$37$$$. Also, notice that the given graph has both self-loops and multiple edges.

Sample Inputs:
3
5 6
2 2 4 1 3
1 2
1 3
2 4
3 4
4 5
5 2
7 7
999999999 999999999 999999999 999999999 1000000000 999999999 1000000000
1 2
2 3
3 4
4 1
4 5
4 6
6 7
14 22
2 3 5 7 3 4 1 4 3 4 2 2 5 1
1 2
2 3
2 4
3 1
4 4
4 5
5 6
5 6
5 12
6 7
6 8
7 5
7 7
7 9
8 4
9 11
10 9
11 10
11 10
12 13
13 14
14 12

Sample Outputs:
5 12
6 5999999995
11 37

Solution (Python):
import io, os
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def find_scc(neigh):
    (scc, s, p) = ([], [], [])
    depth = [0] * len(neigh)
    stack = list(range(len(neigh)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if p[-1] > d:
                scc.append(s[d:])
                del s[d:], p[-1]
                for node in scc[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while p[-1] > depth[node]:
                p.pop()
        elif depth[node] == 0:
            s.append(node)
            p.append(len(s))
            depth[node] = len(s)
            stack.append(~node)
            stack += neigh[node]
    return scc

def main(t):
    (n, m) = map(int, input().split())
    arr = list(map(int, input().split()))
    neigh = [[] for _ in range(n)]
    edges = []
    visited = set()
    for _ in range(m):
        (u, v) = map(int, input().split())
        if u == v:
            continue
        if (u, v) in visited:
            continue
        visited.add((u, v))
        neigh[u - 1].append(v - 1)
        edges.append((u - 1, v - 1))
    scc = find_scc(neigh)
    group = [i for i in range(n)]
    groupnum = [0] * n
    groupsum = [0] * n
    for ele in scc:
        ele.sort()
        groupnum[ele[0]] = len(ele)
        groupsum[ele[0]] = sum([arr[i] for i in ele])
        for i in range(1, len(ele)):
            group[ele[i]] = ele[0]
    pre = [[] for _ in range(n)]
    neigh = [[] for _ in range(n)]
    visited = set()
    for (u, v) in edges:
        if group[u] == group[v]:
            continue
        if (group[u], group[v]) in visited:
            continue
        visited.add((group[u], group[v]))
        neigh[group[u]].append(group[v])
        pre[group[v]].append(group[u])
    outdegree = [len(neigh[i]) for i in range(n)]
    queue = deque()
    dp = [[0, 0]] * n
    for i in range(n):
        if outdegree[i] == 0 and group[i] == i:
            queue.append(i)
    while queue:
        index = queue.popleft()
        maxl = 0
        minv = 0
        for nextindex in neigh[index]:
            if dp[nextindex][0] > maxl:
                maxl = dp[nextindex][0]
                minv = dp[nextindex][1]
            elif dp[nextindex][0] == maxl:
                minv = min(minv, dp[nextindex][1])
        for preindex in pre[index]:
            outdegree[preindex] -= 1
            if outdegree[preindex] == 0:
                queue.append(preindex)
        dp[index] = [maxl + groupnum[index], minv + groupsum[index]]
    (a1, a2) = (-1, 0)
    for [num1, num2] in dp:
        if num1 > a1:
            a1 = num1
            a2 = num2
        elif num1 == a1:
            a2 = min(a2, num2)
    ans = [a1, a2]
    print(*ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def dfs_topo(graph):
    n = len(graph)
    order = []
    used = [0] * n
    for i in range(n):
        if not used[i]:
            st = [(i, 0)]
            while st:
                (node, vis) = st.pop()
                if vis:
                    order.append(node)
                    continue
                if used[node]:
                    continue
                used[node] = 1
                st.append((node, 1))
                for nei in graph[node]:
                    if not used[nei]:
                        st.append((nei, 0))
    return order[::-1]

def find_scc(order, graph, graph_rv):
    n = len(graph_rv)
    exp = [0] * n
    roots = [-1] * n
    comps = [[] for _ in range(n)]
    graph_scc = [[] for _ in range(n)]
    for root in order:
        if not exp[root]:
            tmp = []
            st = [root]
            exp[root] = 1
            roots[root] = root
            while st:
                node = st.pop()
                for nei in graph_rv[node]:
                    if not exp[nei]:
                        exp[nei] = 1
                        st.append(nei)
                        roots[nei] = root
                        tmp.append(nei)
            comps[root] = tmp
    for i in range(n):
        for j in graph[i]:
            if roots[i] != roots[j]:
                graph_scc[roots[j]].append(roots[i])
    return (roots, comps, graph_scc)

def solve():
    (n, m) = readInts()
    a = readList()
    graph = [[] for _ in range(n)]
    graph_rv = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = readInts()
        u -= 1
        v -= 1
        graph[u].append(v)
        graph_rv[v].append(u)
    order = dfs_topo(graph)
    (roots, comps, graph_scc) = find_scc(order, graph, graph_rv)
    vals = [[0, float('inf')] for _ in range(n)]
    for i in range(n):
        if roots[i] != i:
            continue
        vals[i] = [a[i] + sum([a[j] for j in comps[i]]), len(comps[i]) + 1]
    deg = [0] * n
    for i in range(n):
        for j in graph[i]:
            if roots[i] != roots[j]:
                deg[roots[i]] += 1
    st = [i for i in range(n) if deg[i] == 0 and roots[i] == i]
    dp = [[vals[i][0], vals[i][1]] if roots[i] == i else [float('inf'), 0] for i in range(n)]
    while st:
        node = st.pop()
        for p in graph_scc[node]:
            deg[p] -= 1
            if dp[p][1] < vals[p][1] + dp[node][1]:
                dp[p] = [vals[p][0] + dp[node][0], vals[p][1] + dp[node][1]]
            elif dp[p][1] == vals[p][1] + dp[node][1] and dp[p][0] > vals[p][0] + dp[node][0]:
                dp[p] = [vals[p][0] + dp[node][0], vals[p][1] + dp[node][1]]
            if deg[p] == 0:
                st.append(p)
    dp.sort(key=lambda x: (-x[1], x[0]))
    return (dp[0][1], dp[0][0])
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def dfs_topo(graph):
    n = len(graph)
    order = []
    used = [0] * n
    for i in range(n):
        if not used[i]:
            st = [(i, 0)]
            while st:
                (node, vis) = st.pop()
                if vis:
                    order.append(node)
                    continue
                if used[node]:
                    continue
                used[node] = 1
                st.append((node, 1))
                for nei in graph[node]:
                    if not used[nei]:
                        st.append((nei, 0))
    return order[::-1]

def find_scc(order, graph, graph_rv):
    n = len(graph_rv)
    exp = [0] * n
    roots = [-1] * n
    comps = [[] for _ in range(n)]
    graph_scc = [[] for _ in range(n)]
    for root in order:
        if not exp[root]:
            tmp = []
            st = [root]
            exp[root] = 1
            roots[root] = root
            while st:
                node = st.pop()
                for nei in graph_rv[node]:
                    if not exp[nei]:
                        exp[nei] = 1
                        st.append(nei)
                        roots[nei] = root
                        tmp.append(nei)
            comps[root] = tmp
    for i in range(n):
        for j in graph[i]:
            if roots[i] != roots[j]:
                graph_scc[roots[j]].append(roots[i])
    return (roots, comps, graph_scc)

def solve():
    (n, m) = readInts()
    a = readList()
    graph = [[] for _ in range(n)]
    graph_rv = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = readInts()
        u -= 1
        v -= 1
        graph[u].append(v)
        graph_rv[v].append(u)
    (roots, comps, graph_scc) = find_scc(dfs_topo(graph), graph, graph_rv)
    vals = [[0, float('inf')] for _ in range(n)]
    for i in range(n):
        if roots[i] != i:
            continue
        vals[i] = [a[i] + sum([a[j] for j in comps[i]]), len(comps[i]) + 1]
    deg = [0] * n
    for i in range(n):
        for j in graph[i]:
            if roots[i] != roots[j]:
                deg[roots[i]] += 1
    st = [i for i in range(n) if deg[i] == 0 and roots[i] == i]
    dp = [[vals[i][0], vals[i][1]] if roots[i] == i else [float('inf'), 0] for i in range(n)]
    while st:
        node = st.pop()
        for p in graph_scc[node]:
            deg[p] -= 1
            if dp[p][1] < vals[p][1] + dp[node][1]:
                dp[p] = [vals[p][0] + dp[node][0], vals[p][1] + dp[node][1]]
            elif dp[p][1] == vals[p][1] + dp[node][1] and dp[p][0] > vals[p][0] + dp[node][0]:
                dp[p] = [vals[p][0] + dp[node][0], vals[p][1] + dp[node][1]]
            if deg[p] == 0:
                st.append(p)
    dp.sort(key=lambda x: (-x[1], x[0]))
    return (dp[0][1], dp[0][0])
for _ in range(int(input())):
    print(*solve())