Problem:


Bridges

Find bridges of an undirected graph G(V, E).

A bridge (also known as a cut-edge) is an edge whose deletion increase the number of connected components.

Input

|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1

, where |V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (undirected).

Output

A list of bridges of the graph ordered by name. For each bridge, names of its end-ponints, source and target (source < target), should be printed separated by a space. The sources should be printed ascending order, then the target should also be printed ascending order for the same source.

Constraints

1 ≤ |V| ≤ 100,000

0 ≤ |E| ≤ 100,000

The graph is connected

There are no parallel edges

There are no self-loops

Sample Input 1

4 4
0 1
0 2
1 2
2 3

Sample Output 1

2 3

Sample Input 2

5 4
0 1
1 2
2 3
3 4

Sample Output 2

0 1
1 2
2 3
3 4



Sample input:
4 4
0 1
0 2
1 2
2 3


Sample output:
2 3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
st = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param

G = [[] for _ in range(V)]

for s,t in st:
    G[s].append(t)
    G[t].append(s) #not directed

visited = set()
prenum = [0]*V
parent = [0]*V
lowest = [0]*V
timer = 0

def dfs(current,prev):
    global timer
    parent[current]=prev
    prenum[current]=lowest[current]=timer
    timer += 1
    visited.add(current)
    for nex in G[current]:
        if not nex in visited:
            dfs(nex,current)
            lowest[current]=min(lowest[current],lowest[nex])
        elif nex != prev:
            lowest[current]=min(lowest[current],prenum[nex])
dfs(0,-1)
ret = []

for i in range(1,V):
    p = parent[i]
    if prenum[p] < lowest[i]:
        if p < i:
            ret.append([p,i])
        else:
            ret.append([i,p])
ret = sorted(list(ret))

for s,t in ret:
    print(s,t)

Submission status: Accepted

Solution code:
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append(e[1])
            self.graph[e[1]].append(e[0])
            self.deg[e[0]] += 1
            self.deg[e[1]] += 1

    def lowlink(self): #DFS木, ord, lowを計算
        self.ord = [None for _ in range(self.n)]
        self.low = [None for _ in range(self.n)]
        self.group = [None for _ in range(self.n)]
        self.prev = [None for _ in range(self.n)]
        self.tree = [[] for _ in range(self.n)]
        self.sorted = []
        order = 0
        count = 0
        low = [None for _ in range(self.n)]
        for s in range(self.n):
            if self.group[s] is None:
                stack = [(s, None)]
                while stack:
                    node, par = stack.pop()
                    if self.group[node] is None:
                        self.group[node] = count
                        self.ord[node] = order
                        self.sorted.append(node)
                        order += 1
                        if par is not None:
                            self.prev[node] = par
                            self.tree[par].append(node)
                        for adj in self.graph[node]:
                            if self.group[adj] is None:
                                stack.append((adj, node))
                count += 1
        for node in self.sorted[::-1]:
            self.low[node] = self.ord[node]
            for adj in self.graph[node]:
                if self.prev[adj]  == node:
                    self.low[node] = min(self.low[node], self.low[adj])
                elif self.prev[node] == adj:
                    continue
                else:
                    self.low[node] = min(self.low[node], self.ord[adj])

    def articulation(self):
        res = []
        for node in range(self.n):
            if self.prev[node] is None and len(self.tree[node]) > 1:
                res.append(node)
            if self.prev[node] is not None:
                for adj in self.tree[node]:
                    if self.ord[node] <= self.low[adj]:
                        res.append(node)
                        break
        return res

    def bridge(self):
        res = []
        for node in range(self.n):
            for adj in self.tree[node]:
                if self.ord[node] < self.low[adj]:
                    res.append((node, adj))
        return res


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, E)
g.lowlink()
res = g.bridge()
res = list(map(lambda x: (min(x), max(x)), res))
res.sort()
if res:
    print('\n'.join(map(lambda x: ' '.join(map(str, x)), res)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)


def lowLink(N: int, Adj: list):
	articulation = []
	bridge = []
	order = [None] * N
	lowest = [1 << 100] * N

	def _dfs(cur, pre, k):
		order[cur] = lowest[cur] = k
		is_articulation = False
		cnt = 0
		for nxt in Adj[cur]:
			if order[nxt] is None:
				cnt += 1
				_dfs(nxt, cur, k + 1)
				if lowest[cur] > lowest[nxt]:
					lowest[cur] = lowest[nxt]
				is_articulation |= pre >= 0 and lowest[nxt] >= order[cur]
				if order[cur] < lowest[nxt]:
					if cur < nxt:
						bridge.append((cur, nxt))
					else:
						bridge.append((nxt, cur))
			elif nxt != pre and lowest[cur] > order[nxt]:
				lowest[cur] = order[nxt]
		is_articulation |= pre < 0 and cnt > 1
		if is_articulation:
			articulation.append(cur)

	_dfs(0, -1, 0)
	return articulation, bridge


def main():
	n, m, *L = map(int, open(0).read().split())
	adj = [[] for _ in range(n)]
	for s, t in zip(*[iter(L)] * 2):
		adj[s] += t,
		adj[t] += s,
	_, bridge = lowLink(n, adj)
	for x, y in sorted(bridge):
		print(x, y)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def low_link(nodes):
    N = len(nodes)
    visited = [False] * N
    prenum = [0] * N
    parent = [0] * N
    lowest = [0] * N
    bridges = []
    timer = 1

    def rec(cur, prev, timer):
        # curを訪問した直後の処理
        prenum[cur] = lowest[cur] = timer
        timer += 1
        visited[cur] = True
        for nxt in nodes[cur]:
            if not visited[nxt]:
                # curからvへ訪問する直前の処理
                parent[nxt] = cur
                timer = rec(nxt, cur, timer)
                # nxtの探索が終了した直後の処理
                lowest[cur] = min(lowest[cur], lowest[nxt])
                # より近い経路を含まないなら橋とする
                if lowest[nxt] == prenum[nxt]:
                    # 番号の小さい方から入れる
                    bridges.append((min(cur, nxt), max(cur, nxt)))
            elif nxt != prev:
                # cur -> nxt がback-edgeの場合の処理
                lowest[cur] = min(lowest[cur], prenum[nxt])
        return timer
    # 必要な各値の取得(非連結に対応するため全頂点から)
    for i in range(N):
        if not visited[i]:
            timer = rec(i, -1, timer)

    # 間接点
    aps = set()
    # ルートの子ノードの数
    np = 0
    for i in range(1, N):
        p = parent[i]
        if p == 0:
            np += 1
        # 条件2の確認
        elif prenum[p] <= lowest[i]:
            aps.add(p)
    # 条件1の確認
    if np > 1:
        aps.add(0)

    return aps, bridges

N, M = MAP()
nodes = [[] for i in range(N)]
for i in range(M):
    u, v = MAP()
    nodes[u].append(v)
    nodes[v].append(u)

aps, bridges = low_link(nodes)

bridges = sorted(bridges)
for x in bridges:
    print(*x)

Submission status: Accepted

Solution code:
#関節点(そのノードを除くとグラフが非連結になる点)
import sys
class LowLinks:
    def __init__(self, edges, v, root=0):
        self.edges = edges
        self.root = root
        self.ord = [None] * v
        self.low = [None] * v
        self.cnt = 0
        self.bridges = []
        self.articulations = set()
        self.par = [None] * v

    def build(self):
        self.search(self.root)

    def search(self, x):
        self.ord[x] = self.cnt
        self.low[x] = self.cnt
        self.cnt += 1
        dim = 0
        for to in self.edges[x]:
            if to == self.par[x]:continue
            if self.ord[to] != None:
                self.low[x] = min(self.low[x], self.ord[to])
            else:
                self.par[to] = x
                self.search(to)
                dim += 1
                self.low[x] = min(self.low[x], self.low[to])

                if x != self.root and self.ord[x] <= self.low[to]:
                    self.articulations.add(x)

            if x == self.root and dim > 1:
                self.articulations.add(x)

            if self.ord[x] < self.low[to]:
                self.bridges.append((x, to))

sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
for _ in range(m):
    s, t = map(int, input().split())
    edges[s].append(t)
    edges[t].append(s)

l=LowLinks(edges,n)
l.build()
ans=[]
for i,j in l.bridges:
    if i>j:
        ans.append((j,i))
    else:
        ans.append((i,j))
ans.sort()
for i,j in ans:
    print(i,j)

Submission status: Accepted

Solution code:
from typing import List
from typing import Tuple
from functools import cmp_to_key
import sys

sys.setrecursionlimit(100000)

def find_bridges(adj, n) -> List[Tuple[int, int]]:
    mark = [False for _ in range(n)] 
    edges = []
    low_link = [None for _ in range(n)]
    id = [0]

    for v in range(n):
        if not mark[v]:
            ____find_bridges(v, -1, adj, id, low_link, mark, edges)
    return edges


def ____find_bridges(node: int, parent: int, adj, id: List[int], low_link: List[int], mark: List[bool], edges):

    mark[node] = True
    low_link[node] = id[0]
    node_id = id[0]

    for v in adj[node]:
        if v == parent: continue
        if not mark[v]:
            id[0] += 1
            ____find_bridges(v, node, adj, id, low_link, mark, edges)
        low_link[node] = min(low_link[node], low_link[v])
        if low_link[v] > node_id:
            edges.append([node, v])

def read() -> Tuple[List, int]:

    info = [int(e) for e in input().split()]
    n, e = info[0], info[1]
    adj = [[] for _ in range(n)]
    for _ in range(e):
        edge = [int(i) for i in input().split()]
        adj[edge[0]].append(edge[1])
        adj[edge[1]].append(edge[0])
    
    return adj, n

def custom_cmp(edgeA, edgeB):
    if edgeA[0] == edgeB[0]:
        return edgeA[1] - edgeB[1]
    
    return edgeA[0] - edgeB[0]

def process_output(edges: List[List[int]]) -> List[List[int]]:
    for edge in edges:
        edge.sort()
    n_edges = list(sorted(edges, key=cmp_to_key(custom_cmp)))
    return n_edges

def show(edges):
    for edge in edges:
        print('%d %d' % (edge[0], edge[1]))

adj, n = read()
edges = find_bridges(adj, n)
n_edges = process_output(edges)
show(n_edges)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

class LowLink:
    def __init__(self, v):
        self.size = len(v)
        self.v = v
        self.pre = [None]*self.size
        self.low = [None]*self.size
        self.articulation = []
        self.bridge = []
        for x in range(self.size):
            if self.pre[x] is None:
                self.cnt = 0
                self.dfs(x,None)

    def dfs(self, x, par):
        self.pre[x] = self.low[x] = self.cnt
        self.cnt += 1
        is_articulation = False
        n = 0
        for y in self.v[x]:
            if self.pre[y] is None:
                n += 1
                lowy = self.dfs(y, x)
                if lowy < self.low[x]:
                    self.low[x] = lowy
                if self.pre[x] <= lowy:
                    if self.pre[x]:
                        is_articulation = True
                    if self.pre[x] < lowy:
                        self.bridge.append((x,y))
            else:
                if par != y and self.pre[y] < self.low[x]:
                    self.low[x] = self.pre[y]

        if par is None and n > 1:
            is_articulation = True

        if is_articulation:
            self.articulation.append(x)

        return self.low[x]


def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        v[a].append(b)
        v[b].append(a)
    lowlink = LowLink(v)
    bridge = lowlink.bridge
    for i in range(len(bridge)):
        l,r = bridge[i]
        if r < l:
            bridge[i] = (r,l)
    for i in sorted(bridge):
        print(*i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def bridges(E, s):
    N = len(E)
    preorder = [-1] * N # a dfs preordering of each vertex
    lowpt = [N] * N # for finding a cut-vertex
    bridge = []
    stack = [(s, -1, 0)] # (vertex, parent, status)
    pre_num = 0 # current preordering
    while stack:
        v, p, st = stack.pop()
        if st == 0 and preorder[v] < 0: # visited v for the first time
            preorder[v] = pre_num
            lowpt[v] = pre_num
            pre_num += 1
            n_children = 0
            for u in E[v]:
                if preorder[u] >= 0:
                    if u != p: # the edge (v, u) is a back edge, which is not in dfs search tree
                        lowpt[v] = min(lowpt[v], preorder[u])
                    continue
                if n_children == 0:
                    stack += [(v, p, 2), (u, v, 0)]
                    n_children += 1
                else:
                    stack += [(v, p, 1), (u, v, 0)]
                    n_children += 1
            if n_children == 0: # v is a leaf of the dfs search tree
                lowpt[p] = min(lowpt[p], lowpt[v])
                if lowpt[v] > preorder[p]: bridge.append((v, p) if v < p else (p, v))
        elif st == 0 and preorder[v] >= 0: # the edge (v, p) is a back edge
            continue
        elif st == 1: # now searching
            continue
        else: # search finished
            if p != -1:
                lowpt[p] = min(lowpt[p], lowpt[v])
                if lowpt[v] > preorder[p]: bridge.append((v, p) if v < p else (p, v))
    return bridge

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t); E[t].append(s)
br = sorted(bridges(E, 0))
for s, t in br:
    print(s, t)

Submission status: Accepted

Solution code:
# AOJ GRL_3_B
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

import sys

sys.setrecursionlimit(100000)

V, E = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]

ord = [0 for _ in range(0, V)]
low = [0 for _ in range(0, V)]
used = [False for _ in range(0, V)]
bridge = []

G = [ [] for _ in range(0, V)]
for s, t in Edge:
    G[s] += [t]
    G[t] += [s]

# pは親となる頂点
def dfs(s, p, k):
    global articulation
    used[s] = True
    ord[s] = k
    low[s] = ord[s]
    k += 1
    c = 0
    
    # sから始まる辺
    for t in G[s]:
        # まだ探索していないか
        if used[t] == False:
            c += 1
            dfs(t, s, k)
            # DFSの葉の方向進める頂点のlowlinkの最小値
            low[s] = min(low[s], low[t])
        # 後退辺か
        elif t != p:
            # ord[t]の最小値
            low[s] = min(low[s], ord[t])

for s in range(0, V): 
    if used[s] == False:
        dfs(s, -1, 0)

for s, t in Edge:
    if ord[s] < low[t] or ord[t] < low[s]:
        if s < t:
            bridge += [(s, t)]
        else:
            bridge += [(t, s)]

bridge.sort()
for s, t in bridge:
    print(s, t)

Submission status: Accepted

Solution code:
import sys
from typing import List, Set


sys.setrecursionlimit(200000)


def dfs(cur : int, prev: int) -> None:
    global prenum, parent, lowest, counter, bridges
    prenum[cur] = lowest[cur] = counter
    counter += 1
    for edge in edges[cur]:
        if prenum[edge] != sys.maxsize:
            if edge != prev:
                lowest[cur] = min(lowest[cur], prenum[edge])
            continue
        parent[edge] = cur
        dfs(edge, cur)
        lowest[cur] = min(lowest[cur], lowest[edge])
    if prenum[cur] == lowest[cur]:
        bridges.add((cur, prev) if cur < prev else (prev, cur))


if __name__ == "__main__":
    V, E = map(int, input().split())
    edges: List[Set[int]] = [set() for _ in range(V)]

    for _ in range(E):
        s, t = map(int, input().split())
        edges[s].add(t)
        edges[t].add(s)

    prenum = [sys.maxsize] * V
    parent = [sys.maxsize] * V
    lowest = [sys.maxsize] * V
    counter = 0
    bridges = set()  # type: ignore

    dfs(0, -1)
    for bridge in sorted(bridges)[1:]:
        print(*bridge)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
write = sys.stdout.write

N, M = map(int, readline().split())

G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, readline().split())
    G[u].append(v)
    G[v].append(u)

# a chain decomposition
def construct(G, N):
    P = [0]*N
    G0 = [[] for i in range(N)]
    V = []
    lb = [0]*N
    def dfs(v, p):
        P[v] = p
        V.append(v)
        lb[v] = len(V)
        for w in G[v]:
            if w == p:
                continue
            if lb[w]:
                if lb[v] < lb[w]:
                    # a backedge
                    G0[v].append(w)
                continue
            # a tree edge
            dfs(w, v)
    dfs(0, -1)

    used = [0]*N
    first = 1
    B = []
    used[0] = 1
    ap = [0]*N
    for u in V:
        if not used[u]:
            # (u, p) is a bridge
            p = P[u]
            B.append((u, p) if u < p else (p, u))
            if len(G[u]) > 1:
                ap[u] = 1
            if len(G[p]) > 1:
                ap[p] = 1
        cycle = 0
        for v in G0[u]:
            w = v
            while w != u and not used[w]:
                used[w] = 1
                w = P[w]
            if w == u:
                cycle = 1
        if cycle:
            if not first:
                ap[u] = 1
            first = 0
    # v is a cut vertex
    A = [v for v in range(N) if ap[v]]

    return B, A

B, A = construct(G, N)

B.sort()
for u, v in B:
    write("%d %d\n" % (u, v))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline


sys.setrecursionlimit(10**7)
class LowLinks:
    def __init__(self, edges, edges_num:int):
        """edges[u]: all vertexes connected with vertex 'u'
        edges_num: number of edges of graph
        the root of DFS-tree is vertex 0
        """
        self.edges = edges
        self.V = len(edges)
        self.order = [-1]*V
        self.low = [float('inf')]*V
        self.bridges = []
        # if degreee(root) > 1 and graph is tree: root is articulation
        self.articulations = []
        if len(edges[0]) > 1 and edges_num == self.V-1:
            self.articulations.append(0)
        self.k = 0

    def build(self):
        self.dfs(0, 0)

    def get_bridges(self)->tuple:
        return self.bridges

    def get_articulations(self)->tuple:
        return self.articulations

    def dfs(self, v:int, prev:int):
        self.order[v] = self.k
        self.low[v] = self.k
        self.k += 1
        is_articulation = False
        for to in self.edges[v]:
            if self.order[to] < 0: # not visited
                self.dfs(to, v)
                self.low[v] = min(self.low[v], self.low[to])
                if self.order[v] < self.low[to]:
                    self.bridges.append((v, to) if v < to else (to, v))
                is_articulation |= self.order[v] <= self.low[to]
            elif to != prev: # back edge
                self.low[v] = min(self.low[v], self.order[to])
        if v>0 and is_articulation:
            self.articulations.append(v)

if __name__ == "__main__":
    V,E = map(int, readline().split())
    edges = [[] for _ in range(V)]
    for _ in range(E):
        s,t = map(int, readline().split())
        edges[s].append(t)
        edges[t].append(s)
    lowlinks = LowLinks(edges, E)
    lowlinks.build()
    bridges = lowlinks.get_bridges()
    bridges.sort()
    if bridges:
        for s,t in bridges:
            print(s, t)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def input(f):
    global v, e
    global s, t
    
    v, e = map(int, f.readline().split())
    s = [-1 for _ in range(e)]
    t = [-1 for _ in range(e)]
    for i in range(e):
        s[i], t[i] = map(int, f.readline().split())

def solve():
    g = [[] for _ in range(v)]
    for i in range(e):
        g[s[i]].append(t[i])
        g[t[i]].append(s[i])
    
    used = [False for _ in range(v)]
    ord = [-1 for _ in range(v)]
    low = [10**6 for _ in range(v)]
    res = []
    
    def rec(cur, prev, d):
        if used[cur]:
            return
        used[cur] = True
        ord[cur] = d
        low[cur] = ord[cur]
        
        cnt = 0
        for nxt in g[cur]:
            if not used[nxt]:
                cnt += 1
                rec(nxt, cur, d+1)
                low[cur] = min(low[cur], low[nxt])
                if prev >= 0 and ord[cur] < low[nxt]:
                    res.append((min(cur, nxt), max(cur, nxt)))
            elif nxt != prev:
                low[cur] = min(low[cur], ord[nxt])
        
        if prev == -1 and (cnt >= 2 or len(g[cur]) == 1):
            for nxt in g[cur]:
                res.append((min(cur, nxt), max(cur, nxt)))
    
    rec(0, -1, 0)
    
    for src, dst in sorted(res):
        print('{} {}'.format(src, dst))

with open('/dev/stdin') as f:
    input(f)
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e6))

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

edges = {}

for i in range(m):
    s, t = map(int, input().split())
    if s not in edges:
        edges[s] = set()
    if t not in edges:
        edges[t] = set()
    edges[s].add(t)
    edges[t].add(s)

order = [0] * n
lowlink = [0] * n
visited = set()
bridges = set()


def dfs(v, p, i):
    visited.add(v)

    i += 1
    lowlink[v] = order[v] = i

    if v not in edges:
        return

    for t in edges[v]:
        if t not in visited:
            dfs(t, v, i)
            lowlink[v] = min(lowlink[v], lowlink[t])
            if lowlink[t] == order[t]:
                bridges.add((min(v, t), max(v, t)))
        elif t != p:
            lowlink[v] = min(lowlink[v], lowlink[t])


k = 0
for i in range(n):
    if i not in visited:
        dfs(i, -1, k)

for s, t in sorted(bridges):
    print(s, t)

Submission status: Accepted

Solution code:
import sys

class LowLinks:
    def __init__(self, edges, v, root=0):
        self.edges = edges
        self.root = root
        self.ord = [None] * v
        self.low = [None] * v
        self.cnt = 0
        self.bridges = []
        self.articulations = set()
        self.par = [None] * v

    def build(self):
        self.search(self.root)

    def search(self, x):
        self.ord[x] = self.cnt
        self.low[x] = self.cnt
        self.cnt += 1
        dim = 0
        for to in self.edges[x]:
            if to == self.par[x]:continue
            if self.ord[to] != None:
                self.low[x] = min(self.low[x], self.ord[to])
            else:
                self.par[to] = x
                self.search(to)
                dim += 1
                self.low[x] = min(self.low[x], self.low[to])

                if x != self.root and self.ord[x] <= self.low[to]:
                    self.articulations.add(x)

            if x == self.root and dim > 1:
                self.articulations.add(x)

            if self.ord[x] < self.low[to]:
                self.bridges.append((x, to))


sys.setrecursionlimit(1000000)
v, e = map(int, input().split())
edges = [[] for _ in range(v)]
for _ in range(e):
    s, t = map(int, input().split())
    edges[s].append(t)
    edges[t].append(s)

lowlinks = LowLinks(edges, v)
lowlinks.build()
if lowlinks.bridges:
    bridges = sorted(lowlinks.bridges, key=lambda x: (min(x), max(x)))
    for bridge in bridges:
        print(min(bridge), max(bridge))

Submission status: Accepted

Solution code:
# Undirected Graph


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def bridges(graph):
    def visit(v, e):
        nonlocal n
        w = e.other(v)
        if not visited[w]:
            parent[w] = v
            n += 1
            visited[w] = n
            low[w] = n
            return True
        elif w != parent[v]:
            low[v] = min(low[v], visited[w])
            return False

    def leave(p, e):
        c = e.other(p)
        if p == parent[c] and low[c] > visited[p]:
            es.append(e)
        low[p] = min(low[p], low[c])
        return False

    visited = [0] * graph.v
    low = [0] * graph.v
    parent = [-1] * graph.v
    es = []

    s = 0
    n = 1
    visited[s] = n
    low[s] = n
    stack = [(s, e, visit) for e in graph.adj(s)]

    while stack:
        v, e, func = stack.pop()
        # print(v, e.v, e.w, func.__name__, visited, low)
        if func(v, e):
            stack.append((v, e, leave))
            w = e.other(v)
            for ne in graph.adj(w):
                stack.append((w, ne, visit))

    return es


def run():
    v, e = [int(i) for i in input().split()]
    g = Graph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(Edge(s, t))

    edges = [(e.v, e.w) if e.v < e.w else (e.w, e.v)
             for e in bridges(g)]

    for v, w in sorted(edges):
        print(v, w)


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
from collections import deque
sys.setrecursionlimit(1000000)


def dfs(current, prev):
    global time
    # node currentを訪問した直後の処理
    ord[current] = time
    low[current] = time
    time += 1
    color[current] = BLACK

    for next in G[current]:
        if color[next] == WHITE:
            # node currentからnode nextへ訪問する直前の処理
            parent[next] = current
            dfs(next, current)

            # node nextの探索が終了した直後の処理
            low[current] = min(low[current], low[next])
        elif next != prev:
            # edge current --> next がback-edgeの場合の処理
            low[current] = min(low[current], ord[next])


def bridge():
    global time
    time = 1
    dfs(0, -1)  # 0をrootとしてlowの計算
    for u, v in edges:
        if ord[u] < low[v] or ord[v] < low[u]:
            br.add((u, v))


G = {}
edges = set([])
br = set([])
v, n = map(int, input().split())
for i in range(0, v):
    G[i] = []
for i in range(n):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)
    edges.add((s, t))
WHITE = 0
BLACK = 2

color = [WHITE] * (v)
parent = [0] * (v)
ord = [0] * (v)
low = [0] * (v)
parent = [0] * (v)
bridge()
if br:
    for ans in sorted(br):
        print(*ans, sep=' ')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

edges = [set() for _ in range(n)]

for _ in range(m):
    s, t = map(int, input().split())
    edges[s].add(t)
    edges[t].add(s)

prenum = [None] * n
parent = [None] * n
lowest = [None] * n
counter = 0
bridges = set()


def dfs(cur, prev):
    global counter
    prenum[cur] = lowest[cur] = counter
    counter += 1
    for edge in edges[cur]:
        if prenum[edge] is not None:
            if edge != prev:
                lowest[cur] = min(lowest[cur], prenum[edge])
            continue
        parent[edge] = cur
        dfs(edge, cur)
        lowest[cur] = min(lowest[cur], lowest[edge])
    if prenum[cur] == lowest[cur]:
        bridges.add((cur, prev) if cur < prev else (prev, cur))


dfs(0, -1)

for bridge in sorted(bridges)[1:]:
    print(*bridge)