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:
from sys import stdin, stdout
from collections import defaultdict
def readcase(o):
    line = o.readline()
    if not line: return None, None
    line = line.strip().split()
    # print(len(line))
    # print(line[0], line[1])

    return int(line[0]), int(line[1])

def tarjan(g):
    sources = list(g.keys())
    # visited = set()
    artPoints = set()
    time = {}
    low = {}
    parent = {}
    # ancestors = defaultdict(set)
    children = defaultdict(set)
    visitedTime = defaultdict(int)
    ti=0


    def dfs(u, stack):
        nonlocal ti
        while stack:
            u = stack[-1]
            visitedTime[u]+=1
            # Initialize discovery time and low value 
            if u not in time:
                time[u] = ti
                low[u] = ti
                ti += 1 
            currChildren = 0
            for v in g[u]: 
                if v not in time: 
                    parent[v]=u
                    children[u].add(v)
                    currChildren+=1
                    stack.append(v)
                    break
                if v in children[u]:
                    low[u] = min(low[u], low[v]) 
                    if u in parent and low[v] >= time[u]:
                        artPoints.add(u)
                        # print(time[u], low[u], time[v], low[v])
                    if u not in parent and len(children[u])>1:
                        artPoints.add(u)
                        # print(time[u], low[u], time[v], low[v])
                elif u not in parent or parent[u] != v:
                    low[u] = min(low[u], time[v]) 
            if currChildren == 0:
                stack.pop()
    for s in sources:
        if s not in time:
            stack = [s]
            dfs(s, stack)
            ti=0
    ans = sorted(list(artPoints))
    for i, a in enumerate(ans):
        print(a)

if __name__ == '__main__':
    g = defaultdict(list)
    solutions = None
    u, v = readcase(stdin)
    if not (not u or u == 0):
        while 1:   
            u, v = readcase(stdin)
            if u == None:
                break
            if u != v:
                g[u].append(v)
                g[v].append(u)


        tarjan(g)
        # solutions = [str(y) for y in solutions]
        # solutions = "\n".join(solutions)
        # print(solutions, end="")
    # print("2")
    # print(solutions)

Submission status: Accepted

Solution code:
"""
8 10
0 1
1 2
0 2
0 3
3 2
3 4
3 5
5 6
5 7
6 7
"""
import sys
sys.setrecursionlimit(100000)
V,E = map(int,input().split())
C = [[] for _ in range(V)]
for i in range(E):
    tmp = list(map(int,input().split()))
    C[tmp[0]].append(tmp[1])
    C[tmp[1]].append(tmp[0])

INF = 10000000
visited = [False]*V
visit_cnt = 1
prenum = [0]*V
parent = [-1]*V
lowest = [INF]*V

def DFS(node):
    visited[node] = True
    global visit_cnt
    prenum[node] = visit_cnt
    visit_cnt += 1
    for adj in C[node]:
        if not visited[adj]:
            parent[adj] = node
            DFS(adj)

    node_lowest = prenum[node]
    for adj in C[node]:
        if adj != parent[node] and parent[adj] != node:
            if  prenum[adj] < node_lowest:
                node_lowest = prenum[adj]
        else:
            if parent[adj] == node and lowest[adj] < node_lowest:
                node_lowest = lowest[adj]
    lowest[node] = node_lowest
        
root = 0
DFS(root)
ans = []

root_cnt = 0
for p in parent:
    if p == root:
        root_cnt += 1
if root_cnt > 1:
    ans.append(root)

for node in range(V):
    if parent[node] != root and node != root:
        if prenum[parent[node]] <= lowest[node]:
            ans.append(parent[node])
ans = set(ans)
ans = list(ans)
ans.sort()
for i in ans:
    print(i)

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.aps:
    print(v)

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

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.articulation()
if res:
    print('\n'.join(map(str, res)))

Submission status: Accepted

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

N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b = map(int, input().split())

    G[a].append(b)
    G[b].append(a)

INF = 10**10
pre = [0]*N
visited = [0]*N
min_x = [INF]*N
is_articulation = [0]*N
n_root_children = 0


def dfs(v=0, p=-1, k=0):
    global n_root_children
    pre[v] = min_x[v] = mn = k
    visited[v] = 1

    for u in G[v]:
        if u == p:
            continue
        elif visited[u]:
            x = min_x[u]
            if x < mn:
                mn = x
            continue

        if v == 0:
            n_root_children += 1

        k += 1
        x = dfs(u, v, k)

        if pre[v] <= x:
            is_articulation[v] = 1
        if x < mn:
            mn = x

    min_x[v] = mn
    return mn


dfs()

for v, a in enumerate(is_articulation):
    if v == 0:
        if n_root_children >= 2:
            print(v)
    elif a:
        print(v)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

INF = 100000 + 1
V, E = map(int, input().split())
G = [[] * V for _ in range(V)]
visited = [False] * V
prenum = [INF] * V
parent = [INF] * V
lowest = [INF] * V
timer = 1

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

def dfs(cur, prv):
    global timer
    prenum[cur] = lowest[cur] = timer
    timer += 1
    visited[cur] = True
    for nxt in G[cur]:
        if not visited[nxt]:
            parent[nxt] = cur
            dfs(nxt, cur)
            lowest[cur] = min(lowest[cur], lowest[nxt])
        elif nxt != prv:
            lowest[cur] = min(lowest[cur], prenum[nxt])

dfs(0, -1)

np = 0
ap = []
for i in range(V):
    p = parent[i]
    if p == 0:
        np += 1
    elif p != INF and prenum[p] <= lowest[i]:
        ap.append(p)

if np > 1:
    ap.insert(0, 0)

for ans in sorted(set(ap)):
    print(ans)

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(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)
V,E = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")

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)

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 = set()
if sum(1 for p in parent if p==0) > 1:
    ret.add(0)

for i in range(1,V):
    p = parent[i]
    if p != 0 and prenum[p] <= lowest[i]:
        ret.add(p)
ret = sorted(list(ret))

if ret:
    print(*ret,sep='\n')

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]:
					bridge.append((cur, nxt))
			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,
	articulation, _ = lowLink(n, adj)
	if articulation:
		print("\n".join(map(str, sorted(articulation))))


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)

aps = sorted(aps)
for x in aps:
    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()
for i in sorted(l.articulations):
    print(i)

Submission status: Accepted

Solution code:
from typing import List
from typing import Tuple
from sys import setrecursionlimit

setrecursionlimit(100000)

def articulation_points(adj, n):
    low_link = [None for _ in range(n)]
    mark = [False for _ in range(n)]
    id = [-1 for _ in range(n + 1)]
    points = []

    for v in range(n):
        if mark[v]:
            continue
        dfs(v, -1, adj, id, low_link, mark, points)
    points.sort()
    return points

def dfs(v: int, p: int, adj: List[List[int]], id: List[int], low_link: List[int], mark: List[bool], points: List[int]) -> None:
    mark[v] = True
    id[-1] += 1
    id[v] = id[-1]
    low_link[v] = id[v]

    is_articulation_point = False
    childs = 1 if p != -1 else 0 

    for a_v in adj[v]:
        if a_v == p: continue
        if not mark[a_v]:
            childs += 1
            dfs(a_v, v, adj, id, low_link, mark, points)
            low_link[v] = min(low_link[v], low_link[a_v])
            if childs > 1 and id[v] <= low_link[a_v]:
                is_articulation_point = True
        else:
            low_link[v] = min(low_link[v], id[a_v])
    if is_articulation_point:
        points.append(v)

def read() -> Tuple[List[List[int]], int]:
    v, e = tuple([int(i) for i in input().split()])

    adj = [[] for _ in range(v)]

    for i in range(e):
        v1, v2 = tuple([int(j) for j in input().split()])
        adj[v1].append(v2)
        adj[v2].append(v1)
    
    return adj, v

def write(point_list):
    for point in point_list:
        print(point)

adj, n = read()
articulation_point_list = articulation_points(adj, n)
write(articulation_point_list)

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)
    for i in sorted(lowlink.articulation):
        print(i)
    return

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

Submission status: Accepted

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

def run():
  V, E = map(int, input().split())
  if V == 1: exit()
  g = {}
  for e in range(E):
    A, B = map(int, input().split())
    g.setdefault(B, []).append(A)
    g.setdefault(A, []).append(B)
  order = [0]*V
  count = 0
  art = []
  def dfs(now, prev):
    nonlocal count
    fcount = artflag = 0
    count += 1
    low_p = order[now-1] = count
    for nxt in g[now]:
      if nxt == prev:
        continue
      if order[nxt-1] == 0:
        nxt_low_p = dfs(nxt, now)
        artflag |= nxt_low_p >= order[now-1]
        low_p = min(low_p, nxt_low_p)
        fcount += 1
      else:
        low_p = min(low_p, order[nxt-1])
    if (prev == -1 and fcount > 1) or (prev != -1 and artflag):
      art.append(now)
    return low_p
  dfs(1, -1)
  for a in sorted(art):
    print(a)
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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


def DFS(s,p):
    global timer
    prenum[s]=lowest[s]=timer
    timer +=1
    parent[s]=p
    color[s]="gray"

    for i in G[s]:
        if color[i]=="white":
            DFS(i,s)
            lowest[s]=min(lowest[s],lowest[i])
        else:
            lowest[s]=min(lowest[s],prenum[i])
    color[s]="black"


def art_point():
    A=set()
    root=0
    for i,j in enumerate(parent):
        if j==-1:continue
        elif prenum[j]<=lowest[i]:
            A.add(j)
        if j==0:root +=1
    if root==1:A.remove(0)

    return set(A)


v,e=map(int,input().split())
G=[[] for _ in range(v)]

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

prenum=[0 for _ in range(v)]
parent=[0 for _ in range(v)]
lowest=[float("inf") for _ in range(v)]
timer=1
color=["white" for _ in range(v)]

DFS(0,-1)
A=art_point()

for i in sorted(A):
    print(i)

Submission status: Accepted

Solution code:
# Python program to find articulation points in an undirected graph

# #This class represents an undirected graph
# #using adjacency list representation
# class Graph:

# 	def __init__(self,vertices):
# 		self.V= vertices #No. of vertices
# 		self.graph = defaultdict(list) # default dictionary to store graph
# 		self.Time = 0

# 	# function to add an edge to graph
# 	def addEdge(self,u,v):
# 		self.graph[u].append(v)
# 		self.graph[v].append(u)

# 	'''A recursive function that find articulation points
# 	using DFS traversal
# 	u --> The vertex to be visited next
# 	visited[] --> keeps tract of visited vertices
# 	disc[] --> Stores discovery times of visited vertices
# 	parent[] --> Stores parent vertices in DFS tree
# 	ap[] --> Store articulation points'''
# 	def APUtil(self,u, visited, ap, parent, low, disc):

# 		#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] = self.Time
# 		low[u] = self.Time
# 		self.Time += 1

# 		#Recur for all the vertices adjacent to this vertex
# 		for v in self.graph[u]:
# 			# If v is not visited yet, then make it a child of u
# 			# in DFS tree and recur for it
# 			if visited[v] == False :
# 				parent[v] = u
# 				children += 1
# 				self.APUtil(v, visited, ap, 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])

# 				# u is an articulation point in following cases
# 				# (1) u is root of DFS tree and has two or more chilren.
# 				if parent[u] == -1 and children > 1:
# 					ap[u] = True

# 				#(2) If u is not root and low value of one of its child is more
# 				# than discovery value of u.
# 				if parent[u] != -1 and low[v] >= disc[u]:
# 					ap[u] = True

# 				# Update low value of u for parent function calls
# 			elif v != parent[u]:
# 				low[u] = min(low[u], disc[v])


# 	#The function to do DFS traversal. It uses recursive APUtil()
# 	def AP(self):

# 		# Mark all the vertices as not visited
# 		# and Initialize parent and visited,
# 		# and ap(articulation point) arrays
# 		visited = [False] * (self.V)
# 		disc = [float("Inf")] * (self.V)
# 		low = [float("Inf")] * (self.V)
# 		parent = [-1] * (self.V)
# 		ap = [False] * (self.V) #To store articulation points

# 		# Call the recursive helper function
# 		# to find articulation points
# 		# in DFS tree rooted with vertex 'i'
# 		for i in range(self.V):
# 			if visited[i] == False:
# 				self.APUtil(i, visited, ap, parent, low, disc)

# 		for index, value in enumerate (ap):
# 			if value == True: print index,


timer = 0


def find_articulation(node, visited, disc, low, parent, ap, tonodes):
    global timer
    children = 0
    visited[node] = True
    disc[node] = low[node] = timer
    timer += 1
    for nextnode in tonodes[node]:
        if not visited[nextnode]:
            parent[nextnode] = node
            children += 1
            find_articulation(nextnode, visited, disc, low, parent, ap, tonodes)
            low[node] = min(low[node], low[nextnode])
            if parent[node] is None and children > 1:
                # ルートで子供がいる
                ap[node] = True
            if parent[node] is not None and low[nextnode] >= disc[node]:
                # nextnodeから後ろのnodeには遡ることができない
                ap[node] = True
        elif nextnode != parent[node]:
            low[node] = min(low[node], disc[nextnode])


def articulation(tonodes, v):
    visited = [False for _ in range(v)]
    disc = [float("inf") for _ in range(v)]  # 発見の順番を記憶する
    low = [float("inf") for _ in range(v)]  # uの子孫から遡ることができて、prenumが一番小さいuの先祖
    parent = [None for _ in range(v)]  # 深さ優先探索における親
    ap = [False for _ in range(v)]  # 関節点を記録する
    global timer
    timer = 0
    for i in range(v):
        if not visited[i]:
            find_articulation(i, visited, disc, low, parent, ap, tonodes)
    for i in range(v):
        if ap[i]:
            print(i)


def main():
    ve = input().split()
    v, e = tuple(map(int, ve))
    tonodes = [[] for _ in range(v)]
    for _ in range(e):
        st = input().split()
        s, t = tuple(map(int, st))
        tonodes[s].append(t)
        tonodes[t].append(s)
    articulation(tonodes, v)


if __name__ == "__main__":
    import sys
    sys.setrecursionlimit(999999)
    main()

Submission status: Accepted

Solution code:
def cut_vertices(E, s):
    N = len(E)
    preorder = [-1] * N # a dfs preordering of each vertex
    lowpt = [N] * N # for finding a cut-vertex
    cut_vertex = [False] * N
    root_children = 0 # #(children of the root in the dfs search tree)
    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] != 0: cut_vertex[p] = True
                elif preorder[p] == 0: root_children += 1
        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] != 0: cut_vertex[p] = True
                elif preorder[p] == 0: root_children += 1
            else:
                if root_children >= 2: cut_vertex[v] = True
    return cut_vertex

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)
temp = cut_vertices(E, 0)
cut_vs = [v for v in range(N) if temp[v]]
if cut_vs: print(*cut_vs, sep='\n')

Submission status: Accepted

Solution code:
# GRL_3_A : Articulation Point

import sys

sys.setrecursionlimit(100000)

# input
v, e = map(int, sys.stdin.readline().strip().split())
G = [[] for _ in range(v)]
indeg = [0] * v
for i in range(e):
    s, t = map(int, sys.stdin.readline().strip().split())
    G[s].append(t)
    G[t].append(s)
    indeg[t] += 1

# calc
visit = [False] * v
lowest = [v+1] * v
prenum = [-1] * v
parent = [-1] * v
time = 0


def dfs(current, prev):
    global time
    prenum[current] = time
    lowest[current] = time
    visit[current] = True
    time += 1

    for i in G[current]:
        next = i
        if not visit[next]:
            parent[next] = current

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


def art_points():
    dfs(0, -1)

    np = 0  # root が子を2つ以上持つかカウントする
    articulationPoint = [] # 関節点を保存するリスト
    for i in range(1, v):
        if parent[i] == 0:
            np += 1
        elif lowest[i] >= prenum[parent[i]]:
            if parent[i] not in articulationPoint:
                articulationPoint.append(parent[i])

    if np > 1:
        articulationPoint.append(0)

    # articulationPoint = list(set(articulationPoint))
    articulationPoint.sort()

    return articulationPoint


def main():
    ans = art_points()
    for i in ans:
        print(i)


if __name__ == '__main__':
    main()