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

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

Depends on

• cp_library/alg/dp/chmin_fn.py
• cp_library/alg/dp/max2_fn.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/two_edge_connected_components

def main():
    N, M = rd()
    La, Ra, Va, Ea = read_csr_graph(N, M)
    e2ccs, L = two_edge_connected_components(N, M, La, Ra, Va, Ea)
    fast_write_cc(e2ccs, L)

from cp_library.alg.dp.chmin_fn import chmin

def read_csr_graph(N, M):
    U, V, La, Ra, Va, Ea, t = [0]*M, [0]*M, [0]*N, [0]*N, [0]*(M << 1), [-1]*(M << 1), 0
    for e in range(M): U[e], V[e] = rd(); La[U[e]] += 1; La[V[e]] += U[e]!=V[e]
    for u in range(N): La[u] = Ra[u] = (t := t + La[u])
    for e in range(M): La[u := U[e]] -= 1; La[v := V[e]] -= u!=v; Va[La[u]], Va[La[v]] = v, u; Ea[La[u]] = Ea[La[v]] = e
    return La, Ra, Va, Ea

def two_edge_connected_components(N, M, La, Ra, Va, Ea):
    st, buf, e2ccs, L, Ein, tin, low, t, d = [0]*N, elist(N), elist(N), elist(N), [-1]*N, [-1]*N, [-1]*N, -1, -1
    for u in range(N):
        if Ein[u] >= 0: continue
        Ein[u] = M; st[d:=0] = u
        while d >= 0:
            if tin[u := st[d]] == -1: tin[u] = low[u] = (t:=t+1); buf.append(u)
            if (a := La[u]) < Ra[u]:
                La[u] += 1
                if Ein[v := Va[a]] == -1: Ein[v] = Ea[a]; st[d:=d+1] = v
                elif Ea[a] != Ein[u]: chmin(low, u, tin[v])
            elif (d:=d-1) >= 0 and not chmin(low, p := st[d], low[u]) and low[u] > tin[p]:
                L.append(len(e2ccs)); v = -1
                while u != v: e2ccs.append(v := buf.pop())
        L.append(len(e2ccs)); e2ccs.extend(buf); buf.clear()
    return e2ccs, L

from cp_library.ds.list.elist_fn import elist
from cp_library.io.fast_io_fn import rd, wt, wtn

def fast_write_cc(A, L):
    r = len(A); wtn(len(L))
    while L:
        l = L.pop(); wt(str(r-l))
        while l < r: r -= 1; wt(' '); wt(str(A[r]))
        wt('\n')

if __name__ == '__main__':
    main()

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

def main():
    N, M = rd()
    La, Ra, Va, Ea = read_csr_graph(N, M)
    e2ccs, L = two_edge_connected_components(N, M, La, Ra, Va, Ea)
    fast_write_cc(e2ccs, L)

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



def chmin(dp, i, v):
    if ch:=dp[i]>v:dp[i]=v
    return ch

def read_csr_graph(N, M):
    U, V, La, Ra, Va, Ea, t = [0]*M, [0]*M, [0]*N, [0]*N, [0]*(M << 1), [-1]*(M << 1), 0
    for e in range(M): U[e], V[e] = rd(); La[U[e]] += 1; La[V[e]] += U[e]!=V[e]
    for u in range(N): La[u] = Ra[u] = (t := t + La[u])
    for e in range(M): La[u := U[e]] -= 1; La[v := V[e]] -= u!=v; Va[La[u]], Va[La[v]] = v, u; Ea[La[u]] = Ea[La[v]] = e
    return La, Ra, Va, Ea

def two_edge_connected_components(N, M, La, Ra, Va, Ea):
    st, buf, e2ccs, L, Ein, tin, low, t, d = [0]*N, elist(N), elist(N), elist(N), [-1]*N, [-1]*N, [-1]*N, -1, -1
    for u in range(N):
        if Ein[u] >= 0: continue
        Ein[u] = M; st[d:=0] = u
        while d >= 0:
            if tin[u := st[d]] == -1: tin[u] = low[u] = (t:=t+1); buf.append(u)
            if (a := La[u]) < Ra[u]:
                La[u] += 1
                if Ein[v := Va[a]] == -1: Ein[v] = Ea[a]; st[d:=d+1] = v
                elif Ea[a] != Ein[u]: chmin(low, u, tin[v])
            elif (d:=d-1) >= 0 and not chmin(low, p := st[d], low[u]) and low[u] > tin[p]:
                L.append(len(e2ccs)); v = -1
                while u != v: e2ccs.append(v := buf.pop())
        L.append(len(e2ccs)); e2ccs.extend(buf); buf.clear()
    return e2ccs, L




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

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 fast_write_cc(A, L):
    r = len(A); wtn(len(L))
    while L:
        l = L.pop(); wt(str(r-l))
        while l < r: r -= 1; wt(' '); wt(str(A[r]))
        wt('\n')

if __name__ == '__main__':
    main()

Back to top page