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:
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, n):
        p = parent[i]
        if p == 0:
            np += 1
        elif ord[p] <= low[i]:
            ap.append(p)
    if np > 1:
        ap.append(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 = []
art_points()
if ap:
    print(*ap, sep='\n')

Submission status: Wrong Answer

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.append(p)
    if np > 1:
        ap.append(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 = []
art_points()
if ap:
    print(*ap, sep='\n')

Submission status: Wrong Answer

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.append(p)
    if np > 1:
        ap.append(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 = []
art_points()
if ap:
    print(*sorted(ap), sep='\n')

Submission status: Wrong Answer

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 prenum[i] < lowest[child[i][0]]:
        print(i)

Submission status: Wrong Answer

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 prenum[i] <= lowest[child[i][0]]:
        print(i)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Solution code:
__author__ = 'zhewang711'

class Graph:
    def __init__(self):
        self.vertices = 0
        self.outgoing = {}
        self.root_cnt = 0
        # self.incoming = {}

    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)]
        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 = [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, father):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.backing[root] = self.clock
        self.clock += 1
        root_backing = float('inf')
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                ver_backing = self.DFS(ver, root)
                self.backing[root] = min(self.backing[root], self.backing[ver], ver_backing)
            else:
                if ver != father:
                    root_backing = min(self.backing[ver], root_backing)
        return root_backing

    def _critical_points(self, root):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.clock += 1
        is_leaf = True
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                if root == 0:
                    self.root_cnt += 1
                is_leaf = False
                self._critical_points(ver)
        if not is_leaf:
            if self.backing[root] >= self.discovery[root] and root != 0:
                print(root)
g = Graph()
g.get_input()
g.DFS(0, None)
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:
    print(0)

Submission status: Wrong Answer

Solution code:
__author__ = 'zhewang711'

class Graph:
    def __init__(self):
        self.vertices = 0
        self.outgoing = {}
        self.root_cnt = 0
        # self.incoming = {}
        self.result = []

    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)]
        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 = [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, father):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.backing[root] = self.clock
        self.clock += 1
        root_backing = float('inf')
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                ver_backing = self.DFS(ver, root)
                self.backing[root] = min(self.backing[root], self.backing[ver], ver_backing)
            else:
                if ver != father:
                    root_backing = min(self.backing[ver], root_backing)
        return root_backing

    def _critical_points(self, root):
        self.explored[root] = True
        self.discovery[root] = self.clock
        self.clock += 1
        is_leaf = True
        for ver in self.outgoing[root]:
            if not self.explored[ver]:
                if root == 0:
                    self.root_cnt += 1
                is_leaf = False
                self._critical_points(ver)
        if not is_leaf:
            if self.backing[root] >= self.discovery[root] and root != 0:
                self.result.append(root)
g = Graph()
g.get_input()
#g.read_input('1.txt')
g.DFS(0, None)
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.append(0)
l = sorted(g.result)
for i in l:
    print(i)

Submission status: Wrong Answer

Solution code:
__author__ = 'zhewang711'

class Graph:
    def __init__(self):
        self.vertices = 0
        self.outgoing = {}
        self.root_cnt = 0
        # self.incoming = {}
        self.result = []

    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.append(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.append(0)
l = sorted(g.result)
for i in l:
    print(i)

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t = map(int, raw_input().split())
    g[s].append(t)
    g[t].append(s)

ans = set()

memo = [0] * V
used = [0] * V
end = [0] * V
def dfs(v, f):
    cnt = 0
    used[v] = 1
    for t in g[v]:
        if t==f: continue
        if used[t]:
            if not end[t]:
                memo[t] += 1
                cnt += 1
        else:
            res = dfs(t, v)
            if res==0:
                if len(g[v])>1: ans.add(v)
                if len(g[t])>1: ans.add(t)
            cnt -= res
    end[v] = 1
    cnt -= memo[v]
    return cnt
dfs(0, -1)
for e in sorted(ans):
    print e

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t = map(int, raw_input().split())
    g[s].append(t)
    g[t].append(s)

ans = set()

memo = [0] * V
used = [0] * V
end = [0] * V
def dfs(v, f):
    cnt = 0
    used[v] = 1
    for t in g[v]:
        if t==f: continue
        if used[t]:
            if not end[t]:
                memo[t] += 1
                cnt += 1
        else:
            res = dfs(t, v)
            if res==0:
                if len(g[v])>1: ans.add(v)
                if len(g[t])>1: ans.add(t)
            cnt += res
    end[v] = 1
    cnt -= memo[v]
    return cnt
dfs(0, -1)
for e in sorted(ans):
    print e

Submission status: Wrong Answer

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
        lowest[parent[u]] = l
        path.pop()


# output

if parent.count(0) >= 3:
    print(0)

for u in range(2, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        print(p)

Submission status: Wrong Answer

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
        lowest[parent[u]] = l
        path.pop()


# output

ans = set()

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

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

ans = list(ans)
ans.sort()

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

Submission status: Wrong Answer

Solution code:
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
        lowest[parent[u]] = l
        path.pop()


# output

ans = set()

for u in range(2, 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: Wrong Answer

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
        lowest[parent[u]] = l
        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: Wrong Answer

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

"""

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

output:
1
2
3
"""

from sys import stdin

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_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

            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(0, -1)

    v_count = 0
    for j in range(1, vertices):
        parent = parent_v[j]
        if parent == init_vertex_index:
            v_count += 1
        elif pre_v[parent] <= lowest_v[j]:
            ans.append(parent)

    if v_count > 1:
        ans.append(init_vertex_index)

    return ans


if __name__ == '__main__':
    _input = 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))

    timer = 1
    # root
    init_vertex_index = 0

    ans = []
    v_stack = []
    color = [UNVISITED] * vertices

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_matrix(v_info)

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

Submission status: Wrong Answer

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

"""

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

output:
1
2
3
"""

from sys import stdin

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj_matrix(_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

            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(0, -1)

    v_count = 0
    for j in range(1, vertices):
        parent = parent_v[j]
        if parent == init_vertex_index:
            v_count += 1
        elif pre_v[parent] <= lowest_v[j]:
            ans.append(parent)

    if v_count > 1:
        ans.append(init_vertex_index)

    return ans


if __name__ == '__main__':
    _input = 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))

    timer = 1
    # root
    init_vertex_index = 0

    ans = []
    v_stack = []
    color = [UNVISITED] * vertices

    init_adj_table = tuple([] for _ in range(vertices))
    adj_table = generate_adj_matrix(v_info)

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

Submission status: Wrong Answer

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

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(root):
    global timer

    # init the first node of overall graph iterations(times >= 1)
    stack.append(root)
    color[root] = VISITED_IN_STACK
    pre_v[root] = lowest_v[root] = timer
    # init end

    while stack:
        current = stack[-1]
        v_table = adj_table[current]
        # if adj is None, current's adj(s) have been all visited
        adj = v_table.pop() if v_table else None

        if adj:
            if color[adj] is UNVISITED:
                color[adj] = VISITED_IN_STACK
                stack.append(adj)
                parent_v[adj] = current
                timer += 1
                pre_v[adj] = lowest_v[adj] = timer
        else:
            stack.pop()
            color[current] = POPPED_OUT

    return parent_v


def art_points():
    graph_dfs(dfs_root)
    np = 0

    for v in range(1, vertices):
        parent = parent_v[v]
        # print(pre_v[parent], lowest_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()
    # with open('test.txt', 'rt') as _in:
    #     _input = _in.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 = 1
    dfs_root = 0
    stack = []
    pre_v, parent_v, lowest_v = ([float('inf')] * vertices for _ in range(3))

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

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