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

• View this file on GitHub
• Last update: 2025-04-03 08:59:41+09:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• cp_library/alg/dp/chmin_fn.py
• cp_library/ds/elist_fn.py
• cp_library/io/fast/fast_io_fn.py

Code

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

def main():
    N, M = rd(), 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): La[u := rd()] += 1; La[v := rd()] += u!=v; U[e], V[e] = u, v
    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.elist_fn import elist
from cp_library.io.fast.fast_io_fn import rd, wt, wtn, fastio

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

if __name__ == '__main__':
    main()

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

def main():
    N, M = rd(), 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): La[u := rd()] += 1; La[v := rd()] += u!=v; U[e], V[e] = u, v
    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(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
    


from __pypy__.builders import StringBuilder
import sys
from os import read as os_read, write as os_write
from atexit import register as atexist_register

class Fastio:
    ibuf = bytes()
    pil = pir = 0
    sb = StringBuilder()
    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += os_read(0, 131072)
        self.pil = 0; self.pir = len(self.ibuf)
    def flush_atexit(self): os_write(1, self.sb.build().encode())
    def flush(self):
        os_write(1, self.sb.build().encode())
        self.sb = StringBuilder()
    def fastin(self):
        if self.pir - self.pil < 64: self.load()
        minus = x = 0
        while self.ibuf[self.pil] < 45: self.pil += 1
        if self.ibuf[self.pil] == 45: minus = 1; self.pil += 1
        while self.ibuf[self.pil] >= 48:
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus: return -x
        return x
    def fastin_string(self):
        if self.pir - self.pil < 64: self.load()
        while self.ibuf[self.pil] <= 32: self.pil += 1
        res = bytearray()
        while self.ibuf[self.pil] > 32:
            if self.pir - self.pil < 64: self.load()
            res.append(self.ibuf[self.pil])
            self.pil += 1
        return res
    def fastout(self, x): self.sb.append(str(x))
    def fastoutln(self, x): self.sb.append(str(x)); self.sb.append('\n')
fastio = Fastio()
rd = fastio.fastin; rds = fastio.fastin_string; wt = fastio.fastout; wtn = fastio.fastoutln; flush = fastio.flush
atexist_register(fastio.flush_atexit)
sys.stdin = None; sys.stdout = None
def rdl(n): return [rd() for _ in range(n)]
def wtnl(l): wtn(' '.join(map(str, l)))

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

if __name__ == '__main__':
    main()

Back to top page