test/library-checker/graph/incremental_scc.test.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00
• Problem: https://judge.yosupo.jp/problem/incremental_scc

Depends on

• cp_library/alg/dp/max2_fn.py
• cp_library/alg/graph/csr/snippets/scc_incremental_fn.py
• cp_library/alg/iter/arg/argsort_bounded_fn.py
• argsort (cp_library/alg/iter/arg/argsort_fn.py)
• cp_library/bit/pack/packer_cls.py
• cp_library/ds/list/elist_fn.py
• cp_library/io/fast_io_fn.py
• cp_library/io/io_base_cls.py
• cp_library/io/io_cls.py

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/incremental_scc

def main():
    N, M = rd()
    X, U, V = rdl(N), [0]*M, [0]*M
    for e in range(M): U[e], V[e] = rd()
    W, dsu, ans, mod = scc_incremental(N, M, U, V), [*range(N)], [0]*M, 998244353; cur = t = 0
    for e in argsort_bounded(W,M):
        while t < W[e]: ans[t] = cur; t += 1
        u, v = U[e], V[e]
        while u != dsu[u]: dsu[u] = u = dsu[dsu[u]]
        while v != dsu[v]: dsu[v] = v = dsu[dsu[v]]
        if u != v: dsu[v], cur, X[u] = u, (cur+X[u]*X[v])%mod, (X[u]+X[v])%mod
    while t < M: ans[t] = cur; t += 1
    wtnl(ans)

from cp_library.alg.graph.csr.snippets.scc_incremental_fn import scc_incremental
from cp_library.alg.iter.arg.argsort_bounded_fn import argsort_bounded
from cp_library.io.fast_io_fn import rd, rdl, wtnl

if __name__ == '__main__':
    main()

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/incremental_scc

def main():
    N, M = rd()
    X, U, V = rdl(N), [0]*M, [0]*M
    for e in range(M): U[e], V[e] = rd()
    W, dsu, ans, mod = scc_incremental(N, M, U, V), [*range(N)], [0]*M, 998244353; cur = t = 0
    for e in argsort_bounded(W,M):
        while t < W[e]: ans[t] = cur; t += 1
        u, v = U[e], V[e]
        while u != dsu[u]: dsu[u] = u = dsu[dsu[u]]
        while v != dsu[v]: dsu[v] = v = dsu[dsu[v]]
        if u != v: dsu[v], cur, X[u] = u, (cur+X[u]*X[v])%mod, (X[u]+X[v])%mod
    while t < M: ans[t] = cur; t += 1
    wtnl(ans)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''





def scc_incremental(N, M, U, V):
    U, V, W, La, Ra, Va = U[:], V[:], [M]*M, [0]*N, [0]*N, [0]*M
    E, F, sccs, st, buf, tin, low = [*range(M)], [*range(M)], [0]*N, [0]*N, [0]*N, [-1]*N, [-1]*N

    def build_csr(N, E, el, er):
        tot = 0
        for u in range(N): La[u], tin[u] = 0, -1
        i = el
        while i < er: La[U[e := E[i]]] += 1; i += 1
        for u in range(N): La[u] = Ra[u] = (tot := tot + La[u])
        i = el
        while i < er: La[u] = a = La[u := U[e := E[i]]]-1; Va[a] = V[e]; i += 1

    def scc_labels(N, E, el, em, er, La, Ra, Va):
        t = cnt = -1; i = el
        while i < em:
            u = U[E[i]]; i += 1
            if tin[u] < 0:
                st[0] = u; d = b = 0
                while d >= 0:
                    if tin[u := st[d]] == -1: tin[u] = low[u] = (t:=t+1); buf[b] = u; b += 1
                    if La[u] < Ra[u]:
                        if (tv := tin[Va[La[u]]])== -1: st[d:=d+1] = Va[La[u]]
                        elif tv < low[u]: low[u] = tv
                        La[u] += 1
                    else:
                        if (d:=d-1) >= 0 and low[u] < low[st[d]]: low[st[d]] = low[u]
                        if low[u] == tin[u]:
                            v, cnt = -1, cnt+1
                            while u != v: tin[v := buf[b:=b-1]], sccs[buf[b]] = N, cnt
        while i < er:
            u, v = U[E[i]], V[E[i]]; i += 1
            if tin[u] < 0: tin[u], sccs[u] = N, (cnt:=cnt+1)
            if tin[v] < 0: tin[v], sccs[v] = N, (cnt:=cnt+1)
        return cnt+1
    
    def partition(el, er, tm):
        i = em = el
        while i < er:
            if sccs[U[e := E[i]]] == sccs[V[e]]: W[e], F[em] = tm, e; em += 1
            i += 1
        i, fm = el, em
        while i < er:
            if (u := sccs[U[e := E[i]]]) != (v := sccs[V[e]]): U[e], V[e], F[fm] = u, v, e; fm += 1
            i += 1
        return em
    
    def div_con(N, el, er, tl, tr):
        nonlocal E, F
        if el == er: return
        tm, em = (tl+tr) >> 1, el
        while em < er and E[em] <= tm: em += 1
        build_csr(N, E, el, em)
        nN = scc_labels(N, E, el, em, er, La, Ra, Va)
        em = partition(el, er, tm)
        if tr-tl==1: return
        E, F = F, E
        div_con(nN, em, er, tm, tr)
        div_con(N, el, em, tl, tm)
        E, F = F, E
    div_con(N, 0, M, -1, M)
    return W



def argsort(A: list[int], reverse=False):
    P = Packer(len(I := list(A))-1); P.ienumerate(I, reverse); I.sort(); P.iindices(I)
    return I



class Packer:
    __slots__ = 's', 'm'
    def __init__(P, mx: int): P.s = mx.bit_length(); P.m = (1 << P.s) - 1
    def enc(P, a: int, b: int): return a << P.s | b
    def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
    def enumerate(P, A, reverse=False): P.ienumerate(A:=list(A), reverse); return A
    def ienumerate(P, A, reverse=False):
        if reverse:
            for i,a in enumerate(A): A[i] = P.enc(-a, i)
        else:
            for i,a in enumerate(A): A[i] = P.enc(a, i)
    def indices(P, A: list[int]): P.iindices(A:=list(A)); return A
    def iindices(P, A):
        for i,a in enumerate(A): A[i] = P.m&a

def argsort_bounded(A, mx=None, reverse=False):
    N = len(A)
    if mx is None: mx = max(A)
    if N*N.bit_length() < mx or mx < 1000: return argsort(A, reverse)
    I, cnt, t = [0]*N, [0]*(mx+1), 0
    for a in A: cnt[a] += 1
    if reverse:
        for a in range(mx+1): cnt[~a], t = t, t+cnt[~a]
    else:
        for a in range(mx+1): cnt[a], t = t, t+cnt[a]
    for i,a in enumerate(A): I[cnt[a]] = i; cnt[a] += 1
    return I

from os import read as os_read, write as os_write, fstat as os_fstat
import sys
from __pypy__.builders import StringBuilder


def max2(a, b): return a if a > b else b

class IOBase:
    @property
    def char(io) -> bool: ...
    @property
    def writable(io) -> bool: ...
    def __next__(io) -> str: ...
    def write(io, s: str) -> None: ...
    def readline(io) -> str: ...
    def readtoken(io) -> str: ...
    def readtokens(io) -> list[str]: ...
    def readints(io) -> list[int]: ...
    def readdigits(io) -> list[int]: ...
    def readnums(io) -> list[int]: ...
    def readchar(io) -> str: ...
    def readchars(io) -> str: ...
    def readinto(io, lst: list[str]) -> list[str]: ...
    def readcharsinto(io, lst: list[str]) -> list[str]: ...
    def readtokensinto(io, lst: list[str]) -> list[str]: ...
    def readintsinto(io, lst: list[int]) -> list[int]: ...
    def readdigitsinto(io, lst: list[int]) -> list[int]: ...
    def readnumsinto(io, lst: list[int]) -> list[int]: ...
    def wait(io): ...
    def flush(io) -> None: ...
    def line(io) -> list[str]: ...

class IO(IOBase):
    BUFSIZE = 1 << 16; stdin: 'IO'; stdout: 'IO'
    __slots__ = 'f', 'file', 'B', 'O', 'V', 'S', 'l', 'p', 'char', 'sz', 'st', 'ist', 'writable', 'encoding', 'errors'
    def __init__(io, file):
        io.file = file
        try: io.f = file.fileno(); io.sz, io.writable = max2(io.BUFSIZE, os_fstat(io.f).st_size), ('x' in file.mode or 'r' not in file.mode)
        except: io.f, io.sz, io.writable = -1, io.BUFSIZE, False
        io.B, io.O, io.S = bytearray(), [], StringBuilder(); io.V = memoryview(io.B); io.l = io.p = 0
        io.char, io.st, io.ist, io.encoding, io.errors = False, [], [], 'ascii', 'ignore'
    def _dec(io, l, r): return io.V[l:r].tobytes().decode(io.encoding, io.errors)
    def readbytes(io, sz): return os_read(io.f, sz)
    def load(io):
        while io.l >= len(io.O):
            if not (b := io.readbytes(io.sz)):
                if io.O[-1] < len(io.B): io.O.append(len(io.B))
                break
            pos = len(io.B); io.B.extend(b)
            while ~(pos := io.B.find(b'\n', pos)): io.O.append(pos := pos+1)
    def __next__(io):
        if io.char: return io.readchar()
        else: return io.readtoken()
    def readchar(io):
        io.load(); r = io.O[io.l]
        c = chr(io.B[io.p])
        if io.p >= r-1: io.p = r; io.l += 1
        else: io.p += 1
        return c
    def write(io, s: str): io.S.append(s)
    def readline(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p)
    def readtoken(io):
        io.load(); r = io.O[io.l]
        if ~(p := io.B.find(b' ', io.p, r)): s = io._dec(io.p, p); io.p = p+1
        else: s = io._dec(io.p, r-1); io.p = r; io.l += 1
        return s
    def readtokens(io): io.st.clear(); return io.readtokensinto(io.st)
    def readints(io): io.ist.clear(); return io.readintsinto(io.ist)
    def readdigits(io): io.ist.clear(); return io.readdigitsinto(io.ist)
    def readnums(io): io.ist.clear(); return io.readnumsinto(io.ist)
    def readchars(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p-1)
    def readinto(io, lst):
        if io.char: return io.readcharsinto(lst)
        else: return io.readtokensinto(lst)
    def readcharsinto(io, lst): lst.extend(io.readchars()); return lst
    def readtokensinto(io, lst): 
        io.load(); r = io.O[io.l]
        while ~(p := io.B.find(b' ', io.p, r)): lst.append(io._dec(io.p, p)); io.p = p+1
        lst.append(io._dec(io.p, r-1)); io.p = r; io.l += 1; return lst
    def _readint(io, r):
        while io.p < r and io.B[io.p] <= 32: io.p += 1
        if io.p >= r: return None
        minus = x = 0
        if io.B[io.p] == 45: minus = 1; io.p += 1
        while io.p < r and io.B[io.p] >= 48: x = x * 10 + (io.B[io.p] & 15); io.p += 1
        io.p += 1
        return -x if minus else x
    def readintsinto(io, lst):
        io.load(); r = io.O[io.l]
        while io.p < r and (x := io._readint(r)) is not None: lst.append(x)
        io.l += 1; return lst
    def _readdigit(io): d = io.B[io.p] & 15; io.p += 1; return d
    def readdigitsinto(io, lst):
        io.load(); r = io.O[io.l]
        while io.p < r and io.B[io.p] > 32: lst.append(io._readdigit())
        if io.B[io.p] == 10: io.l += 1
        io.p += 1
        return lst
    def readnumsinto(io, lst):
        if io.char: return io.readdigitsinto(lst)
        else: return io.readintsinto(lst)
    def line(io): io.st.clear(); return io.readinto(io.st)
    def wait(io):
        io.load(); r = io.O[io.l]
        while io.p < r: yield
    def flush(io):
        if io.writable: os_write(io.f, io.S.build().encode(io.encoding, io.errors)); io.S = StringBuilder()
sys.stdin = IO.stdin = IO(sys.stdin); sys.stdout = IO.stdout = IO(sys.stdout)
def rd(): return IO.stdin.readints()
def rds(): return IO.stdin.__next__()
def rdl(n): return IO.stdin.readintsinto(elist(n))
def wt(s): IO.stdout.write(s)
def wtn(s): IO.stdout.write(f'{s}\n')
def wtnl(l): IO.stdout.write(' '.join(map(str, l)))



def elist(hint: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint): return []
elist = newlist_hint
    

if __name__ == '__main__':
    main()

Back to top page