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:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

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)

visited=[False]*N
timer=1
prenum=[0]*(N+1)
lowest=[0]*(N+1)
ans=[]
def rec(cur, prev):
    global timer
    # curを訪問した直後の処理
    prenum[cur]=lowest[cur]=timer
    timer+=1

    visited[cur]=True
    for nxt in nodes[cur]:
        # 未訪問なら再帰探索する
        if not visited[nxt]:
            rec(nxt, cur)
            # nxtの探索が終了した直後の処理
            lowest[cur]=min(lowest[cur], lowest[nxt])
            # より近い経路を含まないなら橋とする
            if lowest[nxt]==prenum[nxt]:
                # 番号の小さい方から入れる
                ans.append((min(cur, nxt), max(cur, nxt)))
        # 訪問済の場合、親への経路は無視して、他は近い経路となるか確認を取る
        elif nxt!=prev:
            lowest[cur]=min(lowest[cur], lowest[nxt])

rec(0, -1)

ans.sort()
for edge in ans:
    print(*edge)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

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)

timer=1
prenum=[0]*(N+1)
lowest=[0]*(N+1)
ans=[]
def rec(cur, prev):
    global timer
    # curを訪問した直後の処理
    prenum[cur]=lowest[cur]=timer
    timer+=1

    for nxt in nodes[cur]:
        # 未訪問なら再帰探索する
        if not prenum[nxt]:
            rec(nxt, cur)
            # nxtの探索が終了した直後の処理
            lowest[cur]=min(lowest[cur], lowest[nxt])
            # より近い経路を含まないなら橋とする
            if lowest[nxt]==prenum[nxt]:
                # 番号の小さい方から入れる
                ans.append((min(cur, nxt), max(cur, nxt)))
        # 訪問済の場合、親への経路は無視して、他は近い経路となるか確認を取る
        elif nxt!=prev:
            lowest[cur]=min(lowest[cur], lowest[nxt])

rec(0, -1)

ans.sort()
for edge in ans:
    print(*edge)

Submission status: Accepted

Solution code:
import sys

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:
    br = list(map(sorted, br))
    br.sort(key=lambda x: x[1])
    br.sort(key=lambda x: x[0])
    # 安定ソートだからこれができる
    for ans in br:
        print(*ans)

Submission status: Accepted

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


def main():
    v, e = map(int, readline().split())
    from collections import defaultdict
    g = defaultdict(list)

    for _ in range(e):
        s, t = map(int, readline().split())
        g[s].append(t)
        g[t].append(s)

    visited = set()
    lowest = [None] * v
    parent = [None] * v
    prenum = [None] * v
    child = defaultdict(list)
    root = 0

    # dfs??§tree?????????
    stack = [(root, None)]
    while stack:
        u, prev = stack.pop()
        if u not in visited:
            parent[u] = prev
            if prev is not None:
                child[prev].append(u)
            visited |= {u}
            prenum[u] = lowest[u] = len(visited)

        stack.extend([(v, u) for v in g[u] if v not in visited])

    # lowest????¨????
    from collections import Counter
    leaf = [i for i in range(v) if not child[i]]
    unfinished = Counter()
    for li in leaf:
        while li is not None:
            candidate = [prenum[li]] + [prenum[i] for i in g[li] if i != parent[li]] + [lowest[i] for i in child[li]]
            lowest[li] = min(candidate)
            li = parent[li]
            if li is not None and 1 < len(child[li]):
                unfinished[li] += 1
                if unfinished[li] < len(child[li]):
                    break

    # ????????????
    bridge = []
    for i in range(v):
        if child[i]:
            for j in child[i]:
                if prenum[i] < lowest[j]:
                    bridge.append((i, j) if i < j else (j, i))
    bridge.sort()
    for bi in bridge:
        print(*bi)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

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)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

f_i = sys.stdin

V, E = map(int, f_i.readline().split())

adj = [[] for i in range(V)]

for l_i in f_i:
    s, t = map(int, l_i.split())
    adj[s].append(t)
    adj[t].append(s)


# dfs traverse
prenum = [1] + [None] * (V - 1)
parent = [0] * V
lowest = [1] + [V] * (V - 1)

import collections

path = collections.deque()
path.append(0)

cnt = 1

while path:
    u = path[-1]
    adj_v = adj[u]
    for v in adj_v:
        if not prenum[v]:
            parent[v] = u
            path.append(v)
            cnt += 1
            prenum[v] = cnt
            lowest[v] = cnt
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            lowest[u] = min(lowest[u], lowest[v])
            adj[u].remove(v)
            adj[v].remove(u)
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output
bridge = []

for u in range(1, V):
    p = parent[u]
    if prenum[p] < lowest[u]:
        b = [p, u]
        b.sort()
        bridge.append(b)

bridge.sort()

for b in bridge:
    print(*b)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys
from operator import itemgetter

sys.setrecursionlimit(int(3e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        # undirected graph
        init_adj_table[v_to].append(v_from)
    return init_adj_table


def graph_dfs(u, visited, parent, low, disc):
    global Time
    # Count of children in current node
    children = 0

    # Mark the current node as visited and print it
    visited[u] = True

    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1

    # Recur for all the vertices adjacent to this vertex
    for v in adj_table[u]:
        # If v is not visited yet, then make it a child of u
        # in DFS tree and recur for it
        if not visited[v]:
            parent[v] = u
            children += 1
            graph_dfs(v, visited, parent, low, disc)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            low[u] = min(low[u], low[v])

            ''' If the lowest vertex reachable from subtree
            under v is below u in DFS tree, then u-v is
            a bridge'''
            if low[v] > disc[u]:
                ans.append(sorted([u, v]))
        elif v != parent[u]:  # Update low value of u for parent function calls.
            low[u] = min(low[u], disc[v])

    return None


def bridge():
    visited = [False] * vertices
    disc = [float("Inf")] * vertices
    low = [float("Inf")] * vertices
    parent = [-1] * vertices

    for v in range(vertices):
        if not visited[v]:
            graph_dfs(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    Time = 0
    ans = []

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    res = bridge()
    res.sort()
    for ele in res:
        print(*ele)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys
sys.setrecursionlimit(int(3e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        # undirected graph
        init_adj_table[v_to].append(v_from)
    return init_adj_table


def graph_dfs(u, visited, parent, low, disc):
    global Time
    # Count of children in current node
    children = 0

    # Mark the current node as visited and print it
    visited[u] = True

    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1

    # Recur for all the vertices adjacent to this vertex
    for v in adj_table[u]:
        # If v is not visited yet, then make it a child of u
        # in DFS tree and recur for it
        if not visited[v]:
            parent[v] = u
            children += 1
            graph_dfs(v, visited, parent, low, disc)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            low[u] = min(low[u], low[v])

            ''' If the lowest vertex reachable from subtree
            under v is below u in DFS tree, then u-v is
            a bridge'''
            if low[v] > disc[u]:
                ans.append(sorted([u, v]))
        elif v != parent[u]:  # Update low value of u for parent function calls.
            low[u] = min(low[u], disc[v])

    return None


def bridge():
    visited = [False] * vertices
    disc = [float("Inf")] * vertices
    low = [float("Inf")] * vertices
    parent = [-1] * vertices

    for v in range(vertices):
        if not visited[v]:
            graph_dfs(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    Time = 0
    ans = []

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    res = bridge()
    res.sort()
    for ele in res:
        print(*ele)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys
sys.setrecursionlimit(int(1e5))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        v_from, v_to = map(int, v_detail)
        init_adj_table[v_from].append(v_to)
        # undirected graph
        init_adj_table[v_to].append(v_from)
    return init_adj_table


def graph_dfs(u, visited, parent, low, disc):
    global Time
    # Count of children in current node
    children = 0

    # Mark the current node as visited and print it
    visited[u] = True

    # Initialize discovery time and low value
    disc[u] = Time
    low[u] = Time
    Time += 1

    # Recur for all the vertices adjacent to this vertex
    for v in adj_table[u]:
        # If v is not visited yet, then make it a child of u
        # in DFS tree and recur for it
        if not visited[v]:
            parent[v] = u
            children += 1
            graph_dfs(v, visited, parent, low, disc)

            # Check if the subtree rooted with v has a connection to
            # one of the ancestors of u
            low[u] = min(low[u], low[v])

            ''' If the lowest vertex reachable from subtree
            under v is below u in DFS tree, then u-v is
            a bridge'''
            if low[v] > disc[u]:
                ans.append(sorted([u, v]))
        elif v != parent[u]:  # Update low value of u for parent function calls.
            low[u] = min(low[u], disc[v])

    return None


def bridge():
    visited = [False] * vertices
    disc = [float("Inf")] * vertices
    low = [float("Inf")] * vertices
    parent = [-1] * vertices

    for v in range(vertices):
        if not visited[v]:
            graph_dfs(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    Time = 0
    ans = []

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    res = bridge()
    res.sort()
    for ele in res:
        print(*ele)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys

sys.setrecursionlimit(int(1e5))


def dfs_Tarjan(current, visited, parent, low, disc):
    global timer
    children = 0
    visited[current] = True
    disc[current] = timer
    low[current] = timer
    timer += 1

    for adj in adj_table[current]:
        if not visited[adj]:
            parent[adj] = current
            children += 1
            dfs_Tarjan(adj, visited, parent, low, disc)
            low[current] = min(low[current], low[adj])
            if low[adj] > disc[current]:
                ans.append(sorted([current, adj]))
        elif adj != parent[current]:
            low[current] = min(low[current], disc[adj])

    return None


def dfs_init():
    visited = [False] * v_num
    disc = [float("Inf")] * v_num
    low = [float("Inf")] * v_num
    parent = [-1] * v_num

    for v in range(v_num):
        if not visited[v]:
            dfs_Tarjan(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])
    adj_table = tuple([] for _ in range(v_num))
    for v_info in edges:
        source, target = map(int, v_info)
        adj_table[source].append(target)
        adj_table[target].append(source)

    timer = 0
    ans = list()

    dfs_init()
    # ans.sort()
    for ele in sorted(ans):
        print(*ele)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
5 4
0 1
1 2
2 3
3 4

output:
0 1
1 2
2 3
3 4
"""

import sys

sys.setrecursionlimit(int(1e5))


def dfs_Tarjan(current, visited, parent, low, disc):
    global timer
    children = 0
    visited[current] = True
    disc[current] = timer
    low[current] = timer
    timer += 1

    for adj in adj_table[current]:
        if not visited[adj]:
            parent[adj] = current
            children += 1
            dfs_Tarjan(adj, visited, parent, low, disc)
            low[current] = min(low[current], low[adj])
            if low[adj] > disc[current]:
                ans.append(sorted([current, adj]))
        elif adj != parent[current]:
            low[current] = min(low[current], disc[adj])

    return None


def dfs_init():
    visited = [False] * v_num
    disc = [float("Inf")] * v_num
    low = [float("Inf")] * v_num
    parent = [-1] * v_num

    for v in range(v_num):
        if not visited[v]:
            dfs_Tarjan(v, visited, parent, low, disc)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])
    adj_table = tuple([] for _ in range(v_num))
    for v_info in edges:
        source, target = map(int, v_info)
        adj_table[source].append(target)
        adj_table[target].append(source)
        
    timer = 0
    ans = list()

    dfs_init()
    ans.sort()
    for ele in ans:
        print(*ele)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0

    for i in adj[v]:
        if est[i] == float('inf'):
            child += 1
            parents[i] = v
            dfs(i, tm + 1)
            est[v] = min(est[v], est[i])

            if est[i] > dts[v]: 
                bridges.append((v, i)) if v < i else bridges.append((i, v))

        elif parents[v] != i:
            est[v] = min(est[v], dts[i])

nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
est = [float('inf')] * nv
parents = [None] * nv
dts = [0] * nv
bridges = []

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    adj[t].append(s)

dfs(0, 0)
bridges.sort(key=lambda tup: (tup[0], tup[1]))
[print(str(bridge[0]) + ' ' + str(bridge[1])) for bridge in bridges]

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

v, e = map(int, input().split())

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

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

prenum = [None] * v
parent = [None] * v
lowest = [None] * v
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)

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0] * N]
    for _ in [0] * M:
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    bridges = sorted((a, b) if a < b else (b, a) for a, b in get_lowlink(edges, M)[0])
    for a, b in bridges:
        print(a, b)


def get_lowlink(edges, edge_num):
    import sys
    sys.setrecursionlimit(10**7)

    n = len(edges)
    order = [-1] * n
    low = [float("inf")] * n
    bridges = []
    articulations = [0] if edge_num == n-1 and len(edges[0]) > 1 else []
    append_bridge, append_articulation = bridges.append, articulations.append

    def dfs(v, prev, k):
        order[v] = low[v] = k

        is_articulation = False
        for dest in edges[v]:
            if order[dest] == -1:
                dfs(dest, v, k + 1)
                if low[v] > low[dest]:
                    low[v] = low[dest]
                if order[v] < low[dest]:
                    append_bridge((v, dest))
                is_articulation |= order[v] <= low[dest]

            elif dest != prev and low[v] > order[dest]:
                low[v] = order[dest]

        if v > 0 and is_articulation:
            append_articulation(v)

    dfs(0, 0, 0)
    return bridges, articulations


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def seq():
    a = 1
    while True:
        yield a
        a += 1

def dfs(here, went, connect, discovery, low, answer, seq):
    went |= {here}
    discovery[here] = low[here] = next(seq)
    child = 0
    for con in connect[here]:
        if con not in went:
            parent[con] = here
            child += 1
            dfs(con, went, connect, discovery, low, answer, seq)
            low[here] = min(low[here], low[con])
            if discovery[here] < low[con]:
                answer[min(here,con)].append(max(here,con))
        elif parent[here] != con:
            low[here] = min(low[here], discovery[con])

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = defaultdict(list)
new_seq = seq()
went = set()
discovery = [0 for n in range(vertices)]
low = [float("inf") for n in range(vertices)]
parent = [None for n in range(vertices)]
dfs(0, went, connect, discovery, low, answer, new_seq)

for k in sorted(answer.keys()):
    for n in sorted(answer[k]):
        print(k,n)

Submission status: Accepted

Solution code:
from math import inf
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)


def dfs(v,par):
    global cur
    vis[v]=1 ; disc[v]=cur ;low[v]=cur 
    cur+=1
    for i in g[v]:
        if vis[i]==0:
            dfs(i,v)
            low[v]=min(low[i],low[v])
            if low[i]>disc[v]:
                apts.add((min(v,i),max(v,i)))

        elif i!=par: low[v]=min(disc[i],low[v])
   
def articulation_pts():
    global apts,disc,low,vis
    disc=[0]*n ; low=[inf]*n ; vis=[0]*n ; apts=set()  
    for i in range(n):
        if vis[i]==0:
            dfs(i,-1)

n,e=map(int,input().split())
cur=0
g=[[] for i in range(n)]
for i in range(e):
    x,y=map(int,input().split())
    g[x].append(y)
    g[y].append(x)
articulation_pts()
apts=sorted(apts)
for i in apts:
    print(*i)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # return: articulation points, bridges
    # The graph must be connected.
    def lowlink(adj, root=1):
        N = len(adj) - 1
        order = [N + 1] * (N + 1)
        low = [N + 1] * (N + 1)
        AP = []
        bridge = []

        st = [root]
        cnt = 1
        par = [0] * (N + 1)
        seq = []
        while st:
            v = st.pop()
            if order[v] != N+1:
                continue
            order[v] = cnt
            seq.append(v)
            low[v] = cnt
            cnt += 1
            for u in adj[v]:
                if order[u] < cnt:
                    if par[v] != u:
                        low[v] = min(low[v], order[u])
                        continue
                else:
                    par[u] = v
                    st.append(u)

        child = [[] for _ in range(N + 1)]
        for v in range(1, N + 1):
            child[par[v]].append(v)

        seq.reverse()
        for v in seq:
            for u in child[v]:
                low[v] = min(low[v], low[u])

        # bridge
        for p in range(1, N+1):
            for c in child[p]:
                if order[p] < low[c]:
                    bridge.append((p, c))

        # articulation point
        for v in range(1, N + 1):
            if v == root:
                if len(child[v]) > 1:
                    AP.append(v)
            else:
                for c in child[v]:
                    if order[v] <= low[c]:
                        AP.append(v)
                        break

        return AP, bridge

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        a += 1
        b += 1
        adj[a].append(b)
        adj[b].append(a)

    AP, bridge = lowlink(adj)
    ans = []
    for u, v in bridge:
        u -= 1
        v -= 1
        if u > v:
            u, v = v, u
        ans.append((u, v))
    ans.sort(key=lambda x: x[1])
    ans.sort(key=lambda x: x[0])
    for u, v in ans:
        print(u, v)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	bridges
# CreatedDate:  2020-07-26 23:07:19 +0900
# LastModified: 2020-07-26 23:42:02 +0900
#


import os
import sys
sys.setrecursionlimit(100000)

# import numpy as np
# import pandas as pd


class Graph():
    def __init__(self, V):
        self.V = V
        self.path = [[] for _ in range(self.V)]
        self.parents = [-1] * self.V
        self.lowlink = [float('inf')] * self.V
        self.order = [float('inf')] * self.V
        self.ap = []

    def add(self, s, t):
        self.path[s].append(t)
        self.path[t].append(s)

    def dfs(self, k, u):
        child = 0
        self.lowlink[u] = k
        self.order[u] = k
        k += 1
        for v in self.path[u]:
            if self.lowlink[v] == float('inf'):
                child += 1
                self.parents[v] = u
                self.dfs(k, v)
                self.lowlink[u] = min(self.lowlink[u], self.lowlink[v])

                if self.lowlink[v] > self.order[u]:
                    self.ap.append(sorted([u, v]))

            elif self.parents[u] != v:
                self.lowlink[u] = min(self.lowlink[u], self.order[v])

    def lowlink_order_print(self):
#        print("lowlink:", self.lowlink)
#        print("order:", self.order)
        self.ap = sorted(self.ap)
        for s in self.ap:
            print("{} {}".format(s[0], s[1]))


def main():
    V, E = map(int, input().split())
    graph = Graph(V)
    for _ in range(E):
        s, t = map(int, input().split())
        graph.add(s, t)
    graph.dfs(0, 0)
    graph.lowlink_order_print()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class LowLink():
    def __init__(self,G):
        self.N = len(G)
        self.G = G
        self.low = [-1] * self.N
        self.ord = [-1] * self.N
    
    def _dfs(self,v,time,p = -1):
        self.ord[v] = self.low[v] = time
        time += 1

        isArticulation = False
        cnt = 0
        for e in self.G[v]:
            if self.low[e] < 0:
                cnt += 1
                self._dfs(e,time,v)
                self.low[v] = min(self.low[v],self.low[e])
                if p != -1 and self.ord[v] <= self.low[e]:
                    isArticulation = True
                if self.ord[v] < self.low[e]:
                    if v < e:
                        self.bridge.append((v,e))
                    else:
                        self.bridge.append((e,v))
            elif e != p:
                self.low[v] = min(self.low[v],self.ord[e])
        
        if p == -1 and cnt >= 2:
            isArticulation = True
        if isArticulation:
            self.articulation.append(v) 

    def build(self):
        self.articulation = []
        self.bridge = []
        self._dfs(0,0)
    

def main():
    V,E = map(int,input().split())
    G = [[] for _ in range(V)]
    for _ in range(E):
        a,b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
    
    lowlink = LowLink(G)
    lowlink.build()
    ans = lowlink.bridge
    ans.sort()
    if ans:
        for t in ans:
            print(*t)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 橋検出
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline().rstrip()


# 二つの配列ord,miniを持つ。
V, E = map(int, input().split())
edge = []
graph = [[] for i in range(V)]
for i in range(E):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    edge.append((min(x, y), max(x, y)))

order = [i for i in range(V)]
mini = [V+1 for i in range(V)]
visited = [False for i in range(V)]

used = defaultdict(bool)
for node in range(V):
    for point in graph[node]:
        used[(node, point)] = False
cnt = 0


def dfs(node):
    global cnt
    visited[node] = True
    cnt += 1
    order[node] = cnt
    mini[node] = cnt
    for point in graph[node]:
        if visited[point] == False:
            used[(node, point)] = True
            dfs(point)
            mini[node] = min(mini[node], mini[point])
        elif not used[(point, node)]:
            mini[node] = min(mini[node], order[point])
    return


dfs(0)

answer = []

for x, y in edge:
    if order[x] < order[y]:
        if order[x] < mini[y]:
            answer.append((x, y))
    elif order[x] > order[y]:
        if order[y] < mini[x]:
            answer.append((x, y))
answer.sort()
for x, y in answer:
    print(x, y)

Submission status: Accepted

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

V, E = list(map(int, input().split()))
G = [[] for i in range(V)]

for i in range(E):
    s, t = list(map(int, input().split()))
    G[s].append(t)
    G[t].append(s)

class LowLink:
    def main(G, V):
        LowLink.G = G
        LowLink.used = [False] * V
        LowLink.ord = [0] * V
        LowLink.low = [0] * V
        LowLink.aps = []
        LowLink.bridges = []
        n = 0
        
        for i in range(V):
            if not LowLink.used[i]: n = LowLink.dfs(i, n, -1)
            
        LowLink.aps.sort()
        LowLink.bridges.sort()
        
    def dfs(v, n, par):
        LowLink.used[v] = True
        LowLink.ord[v] = n+1
        n += 1
        LowLink.low[v] = LowLink.ord[v]
        
        is_aps = False
        chi = 0
        
        for u in LowLink.G[v]:
            if not LowLink.used[u]:
                chi += 1
                n = LowLink.dfs(u, n, v)
                LowLink.low[v] = min(LowLink.low[v], LowLink.low[u])
                if par != -1 and LowLink.ord[v] <= LowLink.low[u]: is_aps = True
                if LowLink.ord[v] < LowLink.low[u]: LowLink.bridges.append((min(v, u), max(v, u)))
                
            elif u != par:
                LowLink.low[v] = min(LowLink.low[v], LowLink.ord[u])
                
        if par == -1 and chi >= 2: is_aps = True
        if is_aps: LowLink.aps.append(v)

        return n

LowLink.main(G, V)      

for v in LowLink.bridges:
    print(*v)