Problem:


Articulation Points

Find articulation points of a given undirected graph G(V, E).

A vertex in an undirected graph is an articulation point (or cut vertex) iff removing it disconnects the graph.

Input

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

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

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

Output

A list of articulation points of the graph G ordered by name.

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

Sample Input 2

5 4
0 1
1 2
2 3
3 4

Sample Output 2

1
2
3



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


Sample output:
2

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import heapq
import sys
NIL = -1

def dfs(current, prev):
    global timer
    lowest[current] = timer
    prenum[current] = timer
    timer += 1
    visited[current] = True
    
    for i in range(len(G[current])):
        nex = G[current][i]
        if visited[nex] == False:
            parent[nex] = current
            
            dfs(nex, current)

            
            lowest[current] = min(lowest[current], lowest[nex])
        elif(nex != prev):
            lowest[current] = min(lowest[current], prenum[nex])


sys.setrecursionlimit(1000000)

nums=list(map(int,input().split()))
n = nums[0]
e = nums[1]

G = [[] for j in range(n)]
for i in range(e):
    nums=list(map(int,input().split()))
    G[nums[0]].append(nums[1])
    G[nums[1]].append(nums[0])

S = []
visited = [False] * n
parent = [NIL] * n
prenum = [NIL] * n
lowest = [NIL] * n
timer = 1

dfs(0, -1)

ap = set()
np = 0

for i in range(n):
    p = parent[i]
    if p == 0:
        np += 1
    elif prenum[p] <= lowest[i]:
        ap.add(p)
if np > 1:
    ap.add(0)
ap = list(ap)

heapq.heapify(ap)
for i in range(len(ap)):
    x = heapq.heappop(ap)
    if x != NIL:
        print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(30000)

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

class node:
    def __init__(self, i):
        self.edge=[]
        self.low=0
        self.num=0
        self.visited=False
        self.child=[]
        self.id=i
        
nodes=[node(i) for i in range(v)]
for _ in range(e):
    s,t=map(int,input().split())
    nodes[s].edge.append(t)
    nodes[t].edge.append(s)
    
num=0
def dfs(node):
    global num
    node.num=num
    num+=1
    node.visited=True
    node.low=node.num
    for e in node.edge:
        if not nodes[e].visited:
            dfs(nodes[e])
            node.low=min(node.low, nodes[e].low)
            node.child.append(e)
        else:
            node.low=min(node.low, nodes[e].num)
            
dfs(nodes[0])
            
if len(nodes[0].child)>=2: print(0)
for node in nodes[1:]:
    for e in node.child:
        if node.num <= nodes[e].low:
            print(node.id)
            break

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30


def make_adj_list():
    n, E = map(int, input().strip().split()) # 頂点の数
    l = [[] for _ in range(n)] # 隣接リスト. 各要素は(コスト、to_node)
    for i in range(E):
        s, t = map(int, input().strip().split())
        l[s].append(t)
        l[t].append(s)

    return l, n, E

G = []
prenum = []
parent = []
lowest = []
order = 1
visited = []

def dfs(v, fr):
    global G, prenum, parent, lowest, order, visited
    visited[v] = True
    prenum[v] = lowest[v] = order
    order += 1
    
    for node in G[v]:
        if not visited[node]:
            parent[node] = v
            dfs(node, v)
            lowest[v] = min(lowest[v], lowest[node]) # DFS Treeの子
        elif node != fr:
            lowest[v] = min(lowest[v], prenum[node]) # back edge


def main():
    global G, prenum, parent, lowest, visited
    ans = set()
    G, n, e = make_adj_list()
    prenum = [INF] * n
    parent = [INF] * n
    lowest = [INF] * n
    visited = [False] * n
    dfs(0, -1)

    c = 0
    for i in range(1, n):
        p = parent[i]
        if p == 0:
            c += 1
        elif prenum[p] <= lowest[i]:
            ans.add(p)
    if c >= 2:
        ans.add(0)
    ans = sorted(list(ans))
    for i in ans:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_3_A
# P350に図による説明はあるのだが端折られているところもあり、少し苦しんだ。
# 関節点を求めるには主に2パートに分かれる
# 1. dfsによる各ノードのprenum(深さ優先探索でたどる順番), parent(深さ優先探索でたどる木構造), lowest(こいつはわかりにくいので求め方を図解した)
# 2. 以上で求めた情報に基づいて、そのノードが関節点か決定する。

# 1について`dfs()`で求めて
# 2について`art_points()`で求める
INF = 10**6 + 1
import sys
sys.setrecursionlimit(2**16 - 1)
from collections import defaultdict
G = defaultdict(lambda: [])
# input data
n_V, n_E = list(map(int, input().split()))

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


def get_art_point(G, n_V):
    # graph Gがdefaultdictで定義された隣接リストであること前提とする。
    # n_Vは頂点数
    prenum = [None] * n_V
    parent = [None] * n_V
    lowest = [INF] * n_V
    timer = 0  # dfsに入った順番を記録(prenum用)
    is_visited = [False] * n_V  # 木を作るために循環してはいけない
    root = 0

    # 1のフェーズ、prenumとparent,lowestについて確定していく。
    def dfs(cur, prev):  # 次に訪問するノードが以前のノードprevではないことを識別する必要があるので引数がこうなっている
        # 関数に入るときにprenumとparentを確定してく
        nonlocal timer  # nonlocalは指定した変数が見つかるまでスコープを広げて探す
        prenum[cur] = lowest[cur] = timer  # 教科書の説明とは違ってprenumは0スタートだが本質的な違いはない
        timer += 1
        parent[cur] = prev
        is_visited[cur] = True

        # 次のノードに訪問していく
        for nx in G[cur]:  # nxは次に探索すべきノード
            if (not is_visited[nx]):
                dfs(nx, cur)
                lowest[cur] = min(lowest[cur], lowest[nx]
                                  )  # 子のlowestの最小値が取得できる
            elif nx != prev:  # 探索済みにつながる木以外の経路 いわゆるback-edge
                # back-edge先のノードの方とどっちが小さいか比較
                lowest[cur] = min(lowest[cur], prenum[nx])

    # 2のフェーズ。次にprenumとlowestに注目して間接点を決定してく
    def art_points(root):
        # 間接点の重複を許したくないので集合型で管理
        ret = set()
        n_p_is_root = root  # 螺旋本でいうところのnp。rootから2つ以上の子が存在するならば、rootは間接点
        # 0を根にしているのでその親はNoneであり、これを考慮する必要はない
        for u, p in enumerate(parent):
            if p is None:
                # rootの親はないので
                continue
            elif p == root:
                # uはあるノード。pはその親.
                n_p_is_root += 1

            if prenum[p] <= lowest[u]:
                ret.add(p)
        if n_p_is_root == 1:
            # rootが間接点でないならroot(0)を消す
            ret.remove(0)
        return ret

    # ここから具体的な処理
    dfs(root, None)
    return art_points(root)


ans = list(get_art_point(G, n_V))
ans.sort()
if ans:
    print(*ans, sep='\n')
else:
    pass

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)
    for v in sorted(get_lowlink(edges, M)[1]):
        print(v)


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 typing import List, Set
import sys
sys.setrecursionlimit(1000000) # RecursionError: maximum recursion depth exceeded in comparison 対策

def dfs(current: int, prev: int) -> None:
	global timer
	# ノードcurrentを訪問した直後の処理
	prenum[current] = timer
	lowest[current] = timer
	timer += 1
	visited[current] = True
	for next_v in G[current]:
		if not visited[next_v]:
			# ノードcurrentからノードnext_vへ訪問する直前の処理
			parent[next_v] = current
			dfs(next_v, current)
			# ノードnext_vの探索が終了した直後の処理
			lowest[current] = min(lowest[current], lowest[next_v])
		elif next_v != prev:
			# エッジ(current -> next)がBack-edgeの場合の処理
			lowest[current] = min(lowest[current], prenum[next_v])

def art_points() -> Set[int]:
	# lowestの計算
	dfs(0, -1) # 0：root
	np: int = 0
	ap: Set[int] = set()
	for i in range(1, n):
		p = parent[i]
		if p == 0:
			np += 1
		elif prenum[p] <= lowest[i]:
			ap.add(p)
	if np > 1:
		ap.add(0)
	return ap


if __name__ == "__main__":
	n, m = map(int, input().split())
	G: List[List[int]] = [[] for _ in range(n)]
	prenum: List[int] = [0 for _ in range(n)]
	parent: List[int] = [-1 for _ in range(n)]
	lowest: List[int] = [0 for _ in range(n)]
	visited: List[bool] = [False for _ in range(n)]
	timer = 1
	for _ in range(m):
		s, t = map(int, input().split())
		G[s].append(t)
		G[t].append(s)
	ap = art_points()
	ap = sorted(ap)
	for p in ap:
		print(p)
	# print(prenum)
	# print(parent)
	# print(lowest)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(1000000)


def art_points(n, m, G):
    def dfs(cur, prev):
        nonlocal t
        prenum[cur] = lowest[cur] = t
        t += 1
        visited[cur] = True

        for ne in G[cur]:
            if not visited[ne]:
                parent[ne] = cur
                dfs(ne, cur)
                lowest[cur] = min(lowest[cur], lowest[ne])
            elif ne != prev:
                lowest[cur] = min(lowest[cur], prenum[ne])

    t = 1
    prenum = [0] * n
    parent = [0] * n
    lowest = [0] * n
    visited = [False] * n
    dfs(0, -1)

    ap = set()
    np = 0
    for i, p in zip(range(1, n), parent[1:]):
        if p == 0:
            np += 1
        elif prenum[p] <= lowest[i]:
            ap.add(p)
    if np > 1:
        ap.add(0)
    return ap


def main():
    n, m = [int(x) for x in input().split()]
    G = [[] for _ in range(n)]
    for _ in range(m):
        s, t = [int(x) for x in input().split()]
        G[s].append(t)
        G[t].append(s)
    for p in sorted(art_points(n, m, G)):
        print(p)


main()

Submission status: Accepted

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

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)]
articulation = []

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

def dfs(s, p, k):
    global articulation
    used[s] = True
    ord[s] = k
    low[s] = ord[s]
    k += 1
    c = 0
    for t in G[s]:
        if used[t] == False:
            c += 1
            dfs(t, s, k)
            low[s] = min(low[s], low[t])
            if p != -1 and ord[s] <= low[t]:
                articulation += [s]
        elif t != p:
            low[s] = min(low[s], ord[t])
    if p == -1 and c >= 2:
        articulation += [s]
 
for s in range(0, V): 
    if used[s] == False:
        dfs(s, -1, 0)

answer = list(set(articulation))
answer.sort()
if len(articulation) > 0:
    print("\n".join(list(map(str, answer))))

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
    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 __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

    dfs(0, 1)
    ap: List[bool] = [False] * V
    r = 0
    for _ in filter(lambda x: x == 0, parent):  # type: ignore
        r += 1
        if r > 1:
            ap[0] = True
            break

    for i in range(1, V):
        p = parent[i]
        if p and prenum[p] <= lowest[i]:
            ap[p] = True

    for i, e in enumerate(ap):
        if e:
            print(i)

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)

for v in A:
    write("%d\n" % 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.k += 1
        self.low[v] = self.order[v]
        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.low[v] < self.low[to]:
                    self.bridges.append((v, to))
                is_articulation |= self.order[v] <= self.low[to]
            elif to != prev:
                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()
    articulations = lowlinks.get_articulations()
    if articulations:
        print(*sorted(articulations), sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def solve():
    graph = [[] for _ in range(v)]
    for i in range(e):
        graph[s[i]].append(t[i])
        graph[t[i]].append(s[i])
    
    used = [False for _ in range(v)]
    ord = [0 for _ in range(v)]
    low = [10**6 for _ in range(v)]
    is_articulation = [False for _ in range(v)]
    
    def rec(v, prev, k):
        if used[v]:
            return
        used[v] = True
        k = k+1
        ord[v] = k
        low[v] = ord[v]
        cnt = 0
        for u in graph[v]:
            if not used[u]:
                cnt += 1
                rec(u, v, k)
                low[v] = min(low[v], low[u])
                if prev >= 0 and ord[v] <= low[u]:
                    is_articulation[v] = True
            elif u != prev:
                low[v] = min(low[v], ord[u])
        if prev == -1 and cnt >= 2:
            is_articulation[v] = True
        
        return k
    
    rec(0, -1, 0)
    
    for i in range(v):
        if is_articulation[i]:
            print(i)

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())

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

def read_graph(n, k):
    A = [ [] for _ in range(n) ]
    for _ in range(k):
        line = stdin.readline().strip().split()
        A[int(line[0])].append(int(line[1]))
        A[int(line[1])].append(int(line[0]))
    return A

def art_points(n, A):
    S = deque([])
    color = ["WHITE"] * n
    time = 0
    prenum = [0] * n
    parent = [0] * n
    lowest = [0] * n
    ap = []

    def dfs(u):
        nonlocal S
        nonlocal color
        nonlocal time
        nonlocal prenum
        nonlocal parent
        nonlocal lowest
        S.appendleft(u)
        color[u] = "GRAY"
        prenum[u] = lowest[u] = time
        parent[u] = -1
        time += 1

        while S:
            try:
                w = S[1]
            except IndexError:
                w = -1
            u = S[0]
            colors = [color[v] for v in A[u]]
            if "WHITE" in colors:
                for v in A[u]:
                    if color[v] == "WHITE":
                        parent[v] = u
                        color[v] = "GRAY"
                        prenum[v] = lowest[v] = time
                        time += 1
                        S.appendleft(v)
                        break
            else:
                for v in A[u]:
                    if color[v] == "GRAY" and v != w:
                        # Backedge(u, v) の prenum[v] と比較
                        lowest[u] = min(lowest[u], prenum[v])
                if parent[u] != -1:
                    # 全ての子ノードのlowestと比較
                    lowest[parent[u]] = min(lowest[u], lowest[parent[u]])
                S.popleft()
                color[u] = "BLACK"
                time += 1

    def obtain_ap():
        np = 0
        for i in range(n):
            p = parent[i]
            if p == 0:
                np += 1
            elif prenum[p] <= lowest[i]:
                if p not in ap:
                    ap.append(p)
        if np > 1:
            ap.append(0)

    dfs(0)
    obtain_ap()

    return ap

n, k = [int(i) for i in input().split()]
A = read_graph(n, k)
ap = art_points(n, A)
for i in sorted(ap):
    if i != -1:
        print(i)

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()
articulation = set()


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

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

    is_articulation = False
    cnt = 0

    if v not in edges:
        return

    for t in edges[v]:
        if t not in visited:
            cnt += 1
            dfs(t, v, i)
            lowlink[v] = min(lowlink[v], lowlink[t])
            if p != -1 and order[v] <= lowlink[t]:
                is_articulation = True
        elif t != p:
            lowlink[v] = min(lowlink[v], order[t])

    if p == -1 and cnt > 1:
        is_articulation = True

    if is_articulation:
        articulation.add(v)


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

for art in sorted(articulation):
    print(art)

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.articulations: print(*sorted(lowlinks.articulations),sep="\n")

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)
def inpl():
  return tuple(map(int, input().split()))
V, E = inpl()
graph = [[] for i in range(V)]

for _ in range(E):
  s, t = inpl()
  graph[s].append(t)
  graph[t].append(s)

prenum = [-1] * V
lowest = [float("inf")]*V
found = [False] * V
parent = [-1] *V

result = set()
root = 0

def DFS(i, c, prev):
  global root
  prenum[i] = c
  lowest[i] = c
  found[i] = True

  for p in graph[i]:
    if found[p]:
      if p != prev:
        lowest[i] = min(lowest[i], prenum[p])
    else:
      c = DFS(p, c+1, i)
      lowest[i] = min(lowest[i], lowest[p])

  if prenum[prev] <= lowest[i]:
    result.add(prev)
  parent[i] = prev

  return c

DFS(0, 1, 0)

if parent.count(0) <= 2:
  result = result.difference([0])

for r in sorted(result):
  print(r)

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 articulation_points(graph):
    visited = [0] * graph.v
    low = [0] * graph.v
    parent = [-1] * graph.v

    s = 0
    children = 0
    visit = 0
    stack = [s]
    vs = set()

    while stack:
        v = stack.pop()
        if not visited[v]:
            visit += 1
            visited[v] = visit
            low[v] = visit

        for e in graph.adj(v):
            w = e.other(v)
            if not visited[w]:
                parent[w] = v
                if v == s:
                    children += 1
                stack.append(v)
                stack.append(w)
                break
            elif w != parent[v]:
                low[v] = min(low[v], visited[w])
        else:
            u = parent[v]
            if u < 0:
                pass
            elif parent[u] < 0:
                if children > 1:
                    vs.add(u)
            else:
                if low[v] >= visited[u]:
                    vs.add(u)
                low[u] = min(low[u], low[v])

    return vs


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

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

    for v in sorted(articulation_points(graph)):
        print(v)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

timer = 0

def dfs(current, prev, g, visited, prenum, parent, lowest):
    global timer
    prenum[current] = timer
    lowest[current] = timer
    timer += 1

    visited[current] = True

    for i in range(len(g[current])):
        next_node = g[current][i]
        if not visited[next_node]:
            parent[next_node] = current
            dfs(next_node, current, g, visited, prenum, parent, lowest)
            lowest[current] = min(lowest[current], lowest[next_node])
        elif next_node != prev:
            lowest[current] = min(lowest[current], prenum[next_node])


def art_points(n, g):
    visited = [False] * n
    INFTY = 1 << 20
    prenum = [INFTY] * n
    parent = [INFTY] * n
    parent[0] = -1
    lowest = [INFTY] * n
    global timer
    timer = 1
    dfs(0, -1, g, visited, prenum, parent, lowest)

    ap = set()
    np = 0
    for i in range(1, n):
        p = parent[i]
        if p == 0:
            np += 1
        elif prenum[p] <= lowest[i]:
            ap.add(p)
    if np > 1:
        ap.add(0)
    for line in sorted(ap):
        print(line)


if __name__ == '__main__':
    n, m = [int(v) for v in input().split()]
    g = [[] for i in range(n)]
    for i in range(m):
        s, t = [int(v) for v in input().split()]
        g[s].append(t)
        g[t].append(s)

    art_points(n, g)

Submission status: Runtime Error

Solution code:
from collections import deque


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 art_points():
    global time
    time = 1
    dfs(0, -1)  # 0をrootとしてlowの計算
    np = 0
    for i in range(1, v):
        p = parent[i]
        if p == 0:
            np += 1
        elif ord[p] <= low[i]:
            ap.add(p)
    if np > 1:
        ap.add(0)


G = {}
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)
WHITE = 0
BLACK = 2

color = [WHITE] * (v)
parent = [0] * (v)
ord = [0] * (v)
low = [0] * (v)
parent = [0] * (v)
ap = set([])
art_points()
if ap:
    print(*sorted(ap), sep='\n')

Submission status: Runtime Error

Solution code:
def dfs(u, prev, visited, lowest, parent, prenum):
    # ????????? u ????¨????????????´????????????
    visited |= {u}
    prenum[u] = len(visited)
    lowest[u] = len(visited)

    for v in g[u]:
        if v not in  visited:
            # ????????? u ??????????????? v ????¨????????????´????????????
            parent[v] = u
            dfs(v, u, visited, lowest, parent, prenum)
            # ????????? v ?????¢?´¢?????????????????´????????????
            lowest[u] = min(lowest[u], lowest[v])
        elif v != prev:
            # ??¨?????? u --> v ??? Back-edge ?????´????????????
            lowest[u] = min(lowest[u], prenum[v])
    # ????????? u ?????¢?´¢?????????????????´????????????

from sys import stdin
readline = stdin.readline


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
root = 0
# lowest ????¨????
dfs(root, -1, visited, lowest, parent, prenum)

child = defaultdict(list)
for i in range(v):
    if parent[i] is not None:
        child[parent[i]].append(i)
if 2 <= len(child[root]):
    print(root)
for i in range(1, v):
    if child[i] and any(prenum[i] <= lowest[j] for j in child[i]):
        print(i)

Submission status: Runtime Error

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

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?????????
que = deque([root])
while que:
    u = que.popleft()
    visited |= {u}
    prenum[u] = lowest[u] = len(visited)
    for vi in g[u]:
        if vi not in visited:
            parent[vi] = u
            que.append(vi)

for i in range(v):
    if parent[i] is not None:
        child[parent[i]].append(i)
            
leaf = [i for i in range(v) if not child[i]]
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[i]]
        lowest[li] = min(candidate)
        li = parent[li]

        
if 2 <= len(child[root]):
    print(root)
for i in range(1, v):
    if child[i] and any(prenum[i] <= lowest[j] for j in child[i]):
        print(i)