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: WA: Presentation Error

Solution code:
from sys import stdin
n, m = map(int, stdin.readline().split())
if m < 1:
#    print()
    exit(0)
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
    G[t].append(s)
def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])
dfs(0, -1)
ap = set()
np = 0
for i in range(1, n):
    p = parent[i]
    if p == 0: np += 1
    elif prenum[p] <= lowest[i]:
        ap.add(p)
if np > 1: print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
n, m = map(int, stdin.readline().split())
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
    G[t].append(s)
def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])
dfs(0, -1)
ap = set()
np = 0
for i in range(1, n):
    p = parent[i]
    if p == 0: np += 1
    elif prenum[p] <= lowest[i]:
        ap.add(p)
if np > 1: print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
n, m = map(int, input().split())
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n
for _ in range(m):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)
def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])
dfs(0, -1)
ap = set()
np = 0
for i in range(1, n):
    p = parent[i]
    if p == 0: np += 1
    elif prenum[p] <= lowest[i]:
        ap.add(p)
if np > 1: print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin

n, m = map(int, input().split())
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n

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

def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])

dfs(0, -1)

ap = set()
np = 0

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

if np > 1:
    print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
#from sys import stdin

n, m = map(int, input().split())
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n

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

def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])

dfs(0, -1)

ap = set()
np = 0

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

if np > 1:
    print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
#from sys import stdin

n, m = map(int, input().split())
if m == 0:exit()
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n

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

def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])

dfs(0, -1)

ap = set()
np = 0

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

if np > 1:
    print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
#from sys import stdin

n, m = map(int, input().split())
if m == 0 or n == 0:exit()
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n

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

def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])

dfs(0, -1)

ap = set()
np = 0

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

if np > 1:
    print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
#from sys import stdin

n, m = map(int, input().split())
if m == 0 or n == 0:
    print("")
    exit()
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n

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

def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])

dfs(0, -1)

ap = set()
np = 0

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

if np > 1:
    print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(200000)
n, m = map(int, stdin.readline().split())
G = [[] for _ in [0] * n]
prenum = [0] * n
parent = [0] * n
lowest = [0] * n
timer = 0
visited = [False] * n
for _ in [0] * m:
    s, t = map(int, stdin.readline().split())
    G[s].append(t)
    G[t].append(s)
def dfs(current, prev):
    global timer
    timer += 1
    prenum[current] = lowest[current] = timer
    visited[current] = True
    for i in range(len(G[current])):
        next = G[current][i]
        if not visited[next]:
            parent[next] = current
            dfs(next, current)
            lowest[current] = min(lowest[current], lowest[next])
        elif next != prev:
            lowest[current] = min(lowest[current], prenum[next])
dfs(0, -1)
ap = set()
np = 0
for i in range(1, n):
    p = parent[i]
    if p == 0: np += 1
    elif prenum[p] <= lowest[i]:
        ap.add(p)
if np > 1: print(0)
li = sorted(ap)
print(*li, sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
import sys
from math import isinf
INF = float("inf")
sys.setrecursionlimit(100000)
def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0
    for i in adj[v]:
        if isinf(est[i]):
            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], i)
n, m = map(int, stdin.readline().split())
adj = [[] for _ in range(n)]
est = [INF] * n
parents = [None] * n
aps = [False] * n
dts = [0] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    adj[s].append(t)
    adj[t].append(s)
dfs(0, 0)
print(*[i for i in range(len(aps)) if aps[i]], sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
import sys
from math import isinf
INF = float("inf")
sys.setrecursionlimit(100000)
def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0
    for i in adj[v]:
        if isinf(est[i]):
            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])
n, m = map(int, stdin.readline().split())
adj = [[] for _ in range(n)]
est = [float('inf')] * n
parents = [None] * n
aps = [False] * n
dts = [0] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    adj[s].append(t)
    adj[t].append(s)
dfs(0, 0)
print(*[i for i in range(len(aps)) if aps[i]], sep="\n")

Submission status: WA: Presentation Error

Solution code:
from sys import stdin
#import sys
from math import isinf
INF = float("inf")
#sys.setrecursionlimit(100000)
def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0
    for i in adj[v]:
        if isinf(est[i]):
            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])
n, m = map(int, stdin.readline().split())
adj = [[] for _ in range(n)]
est = [float('inf')] * n
parents = [None] * n
aps = [False] * n
dts = [0] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    adj[s].append(t)
    adj[t].append(s)
dfs(0, 0)
print(*[i for i in range(len(aps)) if aps[i]], sep="\n")

Submission status: WA: Presentation Error

Solution code:
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in [0] * N]
    for _ in [0] * M:
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    print("\n".join(map(str, sorted(get_lowlink(edges)[1]))))


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

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

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

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

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

        if v > 0 and is_articulation:
            append_articulation(v)

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


if __name__ == "__main__":
    solve()

Submission status: WA: Presentation Error

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)

    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.sort()
    print("\n".join(map(str, ap)))