Algorithms and Data Structures Questions

procedure Tarjan(G):
  time = 0
  for v in V:
    if not visited[v]: dfs(v, parent=-1)

procedure dfs(v, parent):
  visited[v]=true
  tin[v]=low[v]=time; time++
  children=0
  for to in adj[v]:
    if to==parent: continue
    if visited[to]:
      low[v]=min(low[v], tin[to])
    else:
      children++
      dfs(to, v)
      low[v]=min(low[v], low[to])
      if low[to] > tin[v]: report bridge (v,to)
      if parent!=-1 and low[to] >= tin[v]: report articulation v
  if parent==-1 and children>1: report articulation v

initialize: for v in V: dsu_cc.make(v); dsu_2ecc.make(v); parent[v]=-1; last_visit[v]=0
lca_iteration=0; bridges=0

procedure make_root(v):
  v = dsu_2ecc.find(v)
  root = v
  child = -1
  while v != -1:
    p = dsu_2ecc.find(parent[v]) if parent[v]!=-1 else -1
    parent[v] = child
    cc_leader = dsu_cc.find(v)
    dsu_cc.union(root, cc_leader)
    child = v
    v = p

procedure merge_path(a, b):
  lca_iteration++
  path_a = []; path_b = []
  while True:
    if a!=-1:
      a = dsu_2ecc.find(a)
      path_a.append(a)
      if last_visit[a]==lca_iteration: lca=a; break
      last_visit[a]=lca_iteration
      a = parent[a]
    if b!=-1:
      b = dsu_2ecc.find(b)
      path_b.append(b)
      if last_visit[b]==lca_iteration: lca=b; break
      last_visit[b]=lca_iteration
      b = parent[b]
  for v in path_a until lca:
    dsu_2ecc.union(v, lca); bridges -=1
  for v in path_b until lca:
    dsu_2ecc.union(v, lca); bridges -=1

procedure add_edge(a,b):
  a = dsu_2ecc.find(a); b = dsu_2ecc.find(b)
  if a==b: return
  ca = dsu_cc.find(a); cb = dsu_cc.find(b)
  if ca != cb:
    bridges +=1
    // link trees: make_root(a); parent[a]=b; dsu_cc.union(ca, cb)
    make_root(a)
    parent[a]=b
    dsu_cc.union(ca, cb)
  else:
    // adding edge inside same connected component may merge 2-edge-comp along path
    merge_path(a,b)

class QueueWithTwoStacks:
    def __init__(self):
        self.inbox = []   # push here on enqueue
        self.outbox = []  # pop here on dequeue

    def enqueue(self, item):
        # O(1)
        self.inbox.append(item)

    def _transfer(self):
        # Move all items from inbox to outbox; O(n) but happens rarely
        while self.inbox:
            self.outbox.append(self.inbox.pop())

    def dequeue(self):
        # Amortized O(1)
        if not self.outbox:
            if not self.inbox:
                raise IndexError("dequeue from empty queue")
            self._transfer()
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            if not self.inbox:
                raise IndexError("peek from empty queue")
            self._transfer()
        return self.outbox[-1]

    def is_empty(self):
        return not (self.inbox or self.outbox)