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: Wrong Answer

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


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    E = [set() for _ in range(n)]
    for _ in range(m):
        s, t = [int(s) for s in input().split(" ")]
        E[s].add(t)
        E[t].add(s)

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

        visited[current] = 1

        for v in E[current]:
            if visited[v] == 0:
                parent[v] = current
                dfs(v, current)
                lowest[current] = min(lowest[current], lowest[v])
            elif v != prev:  # current -> v is back-edge
                lowest[current] = min(lowest[current], prenum[v])

    prenum = [None] * n
    parent = [None] * n
    lowest = [float("inf")] * n
    timer = 1
    visited = [0] * n

    dfs(0, -1)

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

    if np > 1:
        ap.append(0)

    ap = set(ap)
    if ap:
        print("\n".join(map(str, ap)))

Submission status: Wrong Answer

Solution code:
import sys

aumento = 0
def dfs(u,parent,G,id,dfs_num,dfs_low,vis,puntos,acumulador):
    if(u==parent):acumulador+=1
    vis[u]=1
    id+=1
    dfs_num[u] = id
    dfs_low[u] = id
    for v in G[u]:
        if v==parent:continue
        if vis[v]==-1:
            dfs(v,u,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
            if(dfs_low[v]>=dfs_num[u]):
                puntos[u]=True
        else:
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    G = [[] for i in range(V)]
    for j in range(E):
        line =[int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append(line[1])
        G[line[1]].append(line[0])
    n = len(G)
    id=0
    dfs_num = [0 for i in range(n)]
    dfs_low = [0 for i in range(n)]
    vis = [-1 for i in range(n)]
    puntos=[False for i in range(n)]

    for i in range(V):
        if vis[i]==-1:
            acumulador=0
            dfs(i,-1,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            puntos[i]=acumulador>1
    for i in range(len(puntos)):
        if(puntos[i]):print(i)

main()

Submission status: Wrong Answer

Solution code:
import sys

aumento = 0
def dfs(u,parent,G,id,dfs_num,dfs_low,vis,puntos,acumulador):
    if(u==parent):acumulador+=1
    vis[u]=1
    id+=1
    dfs_num[u] = id
    dfs_low[u] = id
    for v in G[u]:
        if v==parent:continue
        if vis[v]==-1:
            dfs(v,u,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            dfs_low[u]=min(dfs_low[u],dfs_low[v])
            if(dfs_low[v]>=dfs_num[u]):
                puntos[u]=True
        else:
            dfs_low[u]=min(dfs_low[u],dfs_num[v])
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    G = [[] for i in range(V)]
    for j in range(E):
        line =[int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append(line[1])
        G[line[1]].append(line[0])
    n = len(G)
    id=0
    dfs_num = [0 for i in range(n)]
    dfs_low = [0 for i in range(n)]
    vis = [-1 for i in range(n)]
    puntos=[False for i in range(n)]

    for i in range(V):
        if vis[i]==-1:
            acumulador=0
            dfs(i,-1,G,id,dfs_num,dfs_low,vis,puntos,acumulador)
            puntos[i]=acumulador>1
    for i in range(len(puntos)):
        if(puntos[i]):print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
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?????????
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])
            
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[li]]
        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)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(s,p,color):
    color[s]=1
    for i in V[s] :
        if color[i]==0 and i!=p:
            dfs(i,p,color)
    color[s]=2

def AP():
    for i in xrange(vn):
        if V[i]!=[]:
            color=[0]*vn
            dfs(V[i][0],i,color)
            color[i]=2
            if color!=[2]*vn:
                ap.append(i)
        else:
            ap.append(i)

vn,e=map(int,raw_input().split())
ap=[]
V=[[] for i in xrange(vn)]
for i in xrange(e):
    s,t=map(int,raw_input().split())
    V[s].append(t)
    V[t].append(s)
if e==0:
    if vn>=3:
        for i in xrange(vn):
            print(i)
    else:
        pass
else:
    AP()
    for i in xrange(len(ap)):
        print(ap[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(s,p,color):
    color[s]=1
    for i in V[s] :
        if color[i]==0 and i!=p:
            dfs(i,p,color)
    color[s]=2

def AP():
    for i in xrange(vn):
        if V[i]!=[]:
            for j in V[i]:
                minpgv=float('inf')
                if pgv[j]<minpgv:
                    minpgv=pgv[j]
                    k=j
            color=[0]*vn
            dfs(k,i,color)
            color[i]=2
            if color!=[2]*vn:
                ap.append(i)
        else:
            ap.append(i)

vn,e=map(int,raw_input().split())
ap=[]
V=[[] for i in xrange(vn)]
pgv=[1]*vn
for i in xrange(e):
    s,t=map(int,raw_input().split())
    V[s].append(t)
    V[t].append(s)
    pgv[s],pgv[t]=pgv[s]+pgv[t],pgv[s]+pgv[t]
if e==0:
    if vn>=3:
        for i in xrange(vn):
            print(i)
    else:
        pass
else:
    AP()
    for i in xrange(len(ap)):
        print(ap[i])

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

                if parents[v] is None and child > 1: aps[v] = True
                if parents[v] is not None and est[i] >= dts[v]: aps[v] = True

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

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

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

dfs(0, 0)

for i in range(nv):
    if aps[i]:
        print(i)

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)
parent=[0]*(N+1)
lowest=[0]*(N+1)
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]:
            # curからvへ訪問する直前の処理
            parent[nxt]=cur
            rec(nxt, cur)
            # vの探索が終了した直後の処理
            lowest[cur]=min(lowest[cur], lowest[nxt])
        elif nxt!=prev:
            # cur -> v がback-edgeの場合の処理
            lowest[cur]=min(lowest[cur], prenum[nxt])

# 必要な各値の取得
rec(0, -1)

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

ap=sorted(ap)
for a in ap:
    print(a)

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

    # ??£???????????????
    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)
main()

Submission status: Accepted

Solution code:
__author__ = 'zhewang711'
import sys
sys.setrecursionlimit(200000)
class Graph:
    def __init__(self):
        self.vertices = 0
        self.outgoing = {}
        self.root_cnt = 0
        # self.incoming = {}
        self.result = set()

    def insert_vertice(self):
        self.vertices += 1
        self.outgoing[self.vertices - 1] = []
        # self.incoming[self.vertices - 1] = {}

    def insert_edge(self, s, d):
        if s >= self.vertices or d >= self.vertices:
            raise ValueError('edge cannot be inserted because vertex do not exist')
        else:
            self.outgoing[s].append(d)
            self.outgoing[d].append(s)

    def get_input(self):
        s = input()
        V, E = int(s.split()[0]), int(s.split()[1])
        self.discovery = [None for i in range(V)]
        self.clock = 0
        self.explored = [False for i in range(V)]
        self.father = [None for i in range(V)]
        self.backing = [None for i in range(V)]
        self.sub_have_backing = [None for i in range(V)]
        self.is_leaf = [None for i in range(V)]
        for i in range(V):
            self.insert_vertice()
        for i in range(E):
            s = input()
            self.insert_edge(int(s.split()[0]), int(s.split()[1]))



    def read_input(self, filename):
        f = open(filename, 'r')
        cnt = 0
        for line in f:
            if cnt == 0:
               cnt += 1
               V, E = int(line.split()[0]), int(line.split()[1])

               self.discovery = [None for i in range(V)]
               self.clock = 0
               self.explored = [False for i in range(V)]
               self.father = [None for i in range(V)]
               self.backing = [None for i in range(V)]
               self.sub_have_backing = [False for i in range(V)]
               self.is_leaf = [None for i in range(V)]

               for i in range(V):
                   self.insert_vertice()
            else:
                self.insert_edge(int(line.split()[0]), int(line.split()[1]))

    def DFS(self, root):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.backing[root] = self.clock
        self.clock += 1
        self.is_leaf[root] = True
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                self.is_leaf[root] = False
                self.DFS(ver)
                self.backing[root] = min(self.backing[root], self.backing[ver])
            else:
                self.backing[root] = min(self.backing[root], self.discovery[ver])

    def _critical_points(self, root):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.clock += 1
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                if root == 0:
                    self.root_cnt += 1
                if self.backing[ver] >= self.discovery[root] and root !=0 and not self.is_leaf[root]:
                    self.result.add(root)
                self._critical_points(ver)

g = Graph()
g.get_input()
#g.read_input('1.txt')
g.DFS(0)
g.clock = 0
g.discovery = [None for i in range(g.vertices)]
g.explored = [False for i in range(g.vertices)]
g._critical_points(0)
if g.root_cnt >= 2:
    g.result.add(0)
l = sorted(g.result)
for i in l:
    print(i)

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


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


dfs(0, 1)
ap = [False] * n
r = 0
for _ in filter(lambda x: x == 0, parent):
    r += 1
    if r > 1:
        ap[0] = True
        break

for i in range(1, n):
    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:
# Acceptance of input

import sys

f_i = sys.stdin

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

adj_sets = [set() for i in range(V)]

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


# dfs traverse

prenum = [0] * V
parent = [0] * V
lowest = [V] * V

import collections

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

cnt = 0

while path:
    u = path[-1]
    adj_v = adj_sets[u].copy()
    v_candidate = adj_v.difference(path)
    if v_candidate:
        v = v_candidate.pop()
        cnt += 1
        prenum[v] = cnt
        parent[v] = u
        path.append(v)
        adj_sets[u].remove(v)
        adj_sets[v].remove(u)
    else:
        l = min(prenum[u], lowest[u])
        for v in adj_v:
            l = min(l, prenum[v])
            adj_sets[u].remove(v)
            adj_sets[v].remove(u)
        lowest[u] = l
        p = parent[u]
        lowest[p] = min(l, lowest[p])
        path.pop()


# output

ans = set()

for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)

if parent.count(0) >= 3:
    ans.add(0)
else:
    ans.discard(0)

ans = list(ans)
ans.sort()

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

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 = [V] * V

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
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            lowest[u] = min(lowest[u], prenum[v])
            adj[u].remove(v)
            adj[v].remove(u)
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output

ans = set()

for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)

if parent.count(0) >= 3:
    ans.add(0)
else:
    ans.discard(0)

ans = list(ans)
ans.sort()

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

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 = [V] * V

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
            adj[u].remove(v)
            adj[v].remove(u)
            break
    if u == path[-1]:
        for v in adj_v:
            lowest[u] = min(lowest[u], prenum[v])
        p = parent[u]
        lowest[p] = min(lowest[u], lowest[p])
        path.pop()


# output

ans = set()

for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)

if parent.count(0) >= 3:
    ans.add(0)
else:
    ans.discard(0)

ans = list(ans)
ans.sort()

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

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(3e6))
UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


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(current, prev):
    global timer
    pre_v[current] = lowest_v[current] = timer
    timer += 1

    color[current] = VISITED_IN_STACK

    for adj in adj_table[current]:
        if color[adj] is UNVISITED:
            parent_v[adj] = current

            # recursive dfs
            graph_dfs(adj, current)

            lowest_v[current] = min(lowest_v[current], lowest_v[adj])
        elif adj is not prev:
            lowest_v[current] = min(lowest_v[current], pre_v[adj])

    return None


def art_points():
    graph_dfs(dfs_root, -1)

    np = 0
    for v in range(1, vertices):
        parent = parent_v[v]
        if parent is dfs_root:
            np += 1
        elif pre_v[parent] <= lowest_v[v]:
            art_set.add(parent)

    if np > 1:
        art_set.add(dfs_root)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    pre_v, parent_v, lowest_v = ([0] * vertices for _ in range(3))
    init_adj_table = tuple([] for _ in range(vertices))

    timer = 1
    # root
    dfs_root = 0

    art_set = set()
    color = [UNVISITED] * vertices

    adj_table = generate_adj_table(v_info)

    res = art_points()
    if not res:
        pass
    else:
        # print(*sorted(art_points()), sep='\n')
        print(*sorted(res), sep='\n')

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(3e6))
UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


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(current, prev):
    global timer
    pre_v[current] = lowest_v[current] = timer
    timer += 1
    # print('time', timer)

    color[current] = VISITED_IN_STACK

    for adj in adj_table[current]:
        if color[adj] is UNVISITED:
            parent_v[adj] = current

            # recursive dfs
            graph_dfs(adj, current)

            lowest_v[current] = min(lowest_v[current], lowest_v[adj])
        elif adj is not prev:
            lowest_v[current] = min(lowest_v[current], pre_v[adj])

    return None


def art_points():
    graph_dfs(dfs_root, -1)

    np = 0
    for v in range(1, vertices):
        parent = parent_v[v]
        if parent is dfs_root:
            np += 1
        elif pre_v[parent] <= lowest_v[v]:
            art_set.add(parent)

    if np > 1:
        art_set.add(dfs_root)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    pre_v, parent_v, lowest_v = ([-1] * vertices for _ in range(3))
    init_adj_table = tuple([] for _ in range(vertices))

    timer = 1
    # root
    dfs_root = 0

    art_set = set()
    color = [UNVISITED] * vertices

    adj_table = generate_adj_table(v_info)

    res = art_points()
    # print('pre', pre_v, 'pr', parent_v, 'lo', lowest_v)
    if not res:
        pass
    else:
        # print(*sorted(art_points()), sep='\n')
        print(*sorted(res), sep='\n')

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(3e6))
UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


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(current, prev):
    global timer
    pre_v[current] = lowest_v[current] = timer
    timer += 1

    color[current] = VISITED_IN_STACK
    for adj in adj_table[current]:
        if color[adj] is UNVISITED:
            parent_v[adj] = current
            # recursive dfs
            graph_dfs(adj, current)
            lowest_v[current] = min(lowest_v[current], lowest_v[adj])
        elif adj is not prev:
            lowest_v[current] = min(lowest_v[current], pre_v[adj])

    return None


def art_points():
    graph_dfs(dfs_root, -1)

    np = 0
    for v in range(1, vertices):
        parent = parent_v[v]
        if parent is dfs_root:
            np += 1
        elif pre_v[parent] <= lowest_v[v]:
            art_set.add(parent)

    if np > 1:
        art_set.add(dfs_root)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    pre_v, parent_v, lowest_v = ([float('inf')] * vertices for _ in range(3))
    init_adj_table = tuple([] for _ in range(vertices))

    timer = 1
    # root
    dfs_root = 0

    art_set = set()
    color = [UNVISITED] * vertices

    adj_table = generate_adj_table(v_info)

    res = art_points()
    # print('parent', parent_v, 'preorder', pre_v, 'postorder', lowest_v)
    if not res:
        pass
    else:
        print(*sorted(res), sep='\n')

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(3e6))
UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


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(current, prev):
    global timer
    pre_v[current] = lowest_v[current] = timer
    timer += 1

    color[current] = VISITED_IN_STACK
    for adj in adj_table[current]:
        if color[adj] is UNVISITED:
            parent_v[adj] = current
            # recursive dfs
            graph_dfs(adj, current)
            lowest_v[current] = min(lowest_v[current], lowest_v[adj])
        elif adj is not prev:
            lowest_v[current] = min(lowest_v[current], pre_v[adj])

    return None


def art_points():
    graph_dfs(dfs_root, -1)

    np = 0
    for v in range(1, vertices):
        parent = parent_v[v]
        if parent is dfs_root:
            np += 1
        elif pre_v[parent] <= lowest_v[v]:
            art_set.add(parent)

    if np > 1:
        art_set.add(dfs_root)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    pre_v, parent_v, lowest_v = ([float('inf')] * vertices for _ in range(3))
    init_adj_table = tuple([] for _ in range(vertices))

    timer = 0
    # root
    dfs_root = 0

    art_set = set()
    color = [UNVISITED] * vertices

    adj_table = generate_adj_table(v_info)

    res = art_points()
    # print('parent', parent_v, 'preorder', pre_v, 'postorder', lowest_v)
    if res:
        print(*sorted(res), sep='\n')

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(3e6))
UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        source, target = map(int, v_detail)
        init_adj_table[source].append(target)
        init_adj_table[target].append(source)
    return init_adj_table


def graph_dfs(current, prev):
    global timer
    pre_v[current] = lowest_v[current] = timer
    timer += 1

    color[current] = VISITED_IN_STACK
    for adj in adj_table[current]:
        if color[adj] is UNVISITED:
            parent_v[adj] = current
            # recursive dfs
            graph_dfs(adj, current)
            lowest_v[current] = min(lowest_v[current], lowest_v[adj])
        elif adj is not prev:
            lowest_v[current] = min(lowest_v[current], pre_v[adj])

    return None


def art_points():
    graph_dfs(root, -1)

    np = 0
    for v in range(1, vertices):
        parent = parent_v[v]
        if parent is root:
            np += 1
        elif pre_v[parent] <= lowest_v[v]:
            art_set.add(parent)

    if np > 1:
        art_set.add(root)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    pre_v, parent_v, lowest_v = ([float('inf')] * vertices for _ in range(3))
    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    timer = 0
    root = 0
    art_set = set()
    color = [UNVISITED] * vertices

    res = art_points()
    if res:
        print(*sorted(res), sep='\n')

Submission status: Accepted

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

"""

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

output:
1
2
3
"""

import sys

sys.setrecursionlimit(int(1e6))


def generate_adj_table(_v_info):
    for v_detail in _v_info:
        source, target = map(int, v_detail)
        init_adj_table[source].append(target)
        init_adj_table[target].append(source)
    return init_adj_table


def Tarjan(current, parents, visited, disc, low):
    global timer
    current_children_count = 0
    visited[current] = True
    disc[current] = low[current] = timer
    timer += 1

    for adj in adj_table[current]:
        if not visited[adj]:
            parents[adj] = current
            current_children_count += 1

            Tarjan(adj, parents, visited, disc, low)

            low[current] = min(low[current], low[adj])
            # current is root of DFS tree
            if parents[current] == -1 and current_children_count > 1:
                art_set.add(current)

            elif parents[current] != -1 and low[adj] >= disc[current]:
                art_set.add(current)

        elif adj != parents[current]:
            low[current] = min(low[current], disc[adj])

    # print(timer, parents, visited, disc, low)
    return None


def art_points():
    parents = [-1] * vertices
    visited = [False] * vertices
    disc = [float('inf')] * vertices
    low = [float('inf')] * vertices

    for v in range(vertices):
        Tarjan(v, parents, visited, disc, low)

    return art_set


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    v_info = map(lambda x: x.split(), _input[1:])
    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    timer = 0
    art_set = set()
    ans = art_points()
    if ans:
        print(*sorted(ans), sep='\n')