Problem p03306 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

maxS = 0
vMaxS = -1
adjL = [[] for v in range(n)]
for i in range(m):
    u, v, s = map(int, input().split())
    adjL[u-1].append((v-1, s))
    adjL[v-1].append((u-1, s))
    if s > maxS:
        maxS = s
        vMaxS = u-1

# sの最大値が2の場合は、全ての頂点に1を書くケースのみが条件を満たす
if maxS == 2:
    print(1)
    exit()

#
def DFS(vNow):
    if len(zRange[vNow]) > 1: return
    zFr, zTo, dz = zRange[vNow][0]
    for v2, s in adjL[vNow]:
        # 頂点vNowの整数範囲と辺の整数sから定まる、頂点v2の整数範囲を条件リストに追加する
        zRange[v2].append((s - zFr, s - zTo, -dz))
        DFS(v2)


zRange = [[] for v in range(n)]
zRange[vMaxS].append((1, maxS-1, 1)) # 頂点vMaxSの整数範囲[1, maxS-1]、1は傾きの意
DFS(vMaxS)


# 各頂点について、課せられた整数範囲条件の共通部分を求める
iRange = [[] for v in range(n)]
for v, zR in enumerate(zRange):
    zR = list(set(zR)) # 重複を排除する
    if len(zR) > 2:
        # 3つ以上の条件が残っている場合、共通部分はない
        print(0)
        exit()
    elif len(zR) == 2:
        s1, ds = zR[0][0], zR[0][2]
        t1, dt = zR[1][0], zR[1][2]
        if ds == dt:
            # 傾きは同じだが範囲が異なる場合、共通部分はない
            print(0)
            exit()
        else:
            # 傾きが異なる場合、交点を求める
            iC = (s1 - t1) / (dt - ds)
            if iC == int(iC) and 0 <= iC <= maxS-2 and s1 + ds * iC > 0:
                iRange[v] = [int(iC), int(iC)]
            else:
                print(0)
                exit()
    else:
        # 条件が1つの場合、「正の整数」である範囲を求める
        s1, ds = zR[0][0], zR[0][2]
        if ds == 1:
            iFr, iTo = max(0, 1-s1), maxS-2
        else:
            iFr, iTo = 0, min(s1-1, maxS-2)

        if iFr <= iTo:
            iRange[v] = [iFr, iTo]
        else:
            print(0)
            exit()

# 全ての頂点の共通範囲をまとめる
iRange = list(zip(*iRange)) # 転置
iFr = max(iRange[0])
iTo = min(iRange[1])
if iFr <= iTo:
    print(iTo - iFr + 1)
else:
    print(0)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())

maxS = 0
vMaxS = -1
adjL = [[] for v in range(n)]
for i in range(m):
    u, v, s = map(int, input().split())
    adjL[u-1].append((v-1, s))
    adjL[v-1].append((u-1, s))
    if s > maxS:
        maxS = s
        vMaxS = u-1

# sの最大値が2の場合は、全ての頂点に1を書くケースのみが条件を満たす
if vMaxS == 2:
    print(1)
    exit()

#
def DFS(vNow):
    if len(zRange[vNow]) > 1: return
    zFr, zTo, dz = zRange[vNow][0]
    for v2, s in adjL[vNow]:
        # 頂点vNowの整数範囲と辺の整数sから定まる、頂点v2の整数範囲を条件リストに追加する
        zRange[v2].append((s - zFr, s - zTo, -dz))
        DFS(v2)


zRange = [[] for v in range(n)]
zRange[vMaxS].append((1, maxS-1, 1)) # 頂点vMaxSの整数範囲[1, maxS-1]、1は傾きの意
DFS(vMaxS)


# 各頂点について、課せられた整数範囲条件の共通部分を求める
iRange = [[] for v in range(n)]
for v, zR in enumerate(zRange):
    zR = list(set(zR)) # 重複を排除する
    if len(zR) > 2:
        # 3つ以上の条件が残っている場合、共通部分はない
        print(0)
        exit()
    elif len(zR) == 2:
        s1, ds = zR[0][0], zR[0][2]
        t1, dt = zR[1][0], zR[1][2]
        if ds == dt:
            # 傾きは同じだが範囲が異なる場合、共通部分はない
            print(0)
            exit()
        else:
            # 傾きが異なる場合、交点を求める
            iC = (s1 - t1) / (dt - ds)
            if iC == int(iC) and 0 <= iC <= maxS-2 and s1 + ds * iC > 0:
                iRange[v] = [int(iC), int(iC)]
            else:
                print(0)
                exit()
    else:
        # 条件が1つの場合、「正の整数」である範囲を求める
        s1, ds = zR[0][0], zR[0][2]
        if ds == 1:
            iFr, iTo = [max(0, 1-s1), maxS-2]
        else:
            iFr, iTo = [0, min(s1-1, maxS-2)]

        if iFr <= iTo:
            iRange[v] = [iFr, iTo]
        else:
            print(0)
            exit()

# 全ての頂点の共通範囲をまとめる
iRange = list(zip(*iRange)) # 転置
iFr = max(iRange[0])
iTo = min(iRange[1])
if iFr <= iTo:
    print(iTo - iFr + 1)
else:
    print(0)