We Need More Bosses (Codeforces 1000E)
Tags: Others, trees

Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $$$n$$$ locations connected by $$$m$$$ two-way passages. The passages are designed in such a way that it should be possible to get from any location to any other location.Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called bosses). And your friend wants you to help him place these bosses.The game will start in location $$$s$$$ and end in location $$$t$$$, but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from $$$s$$$ to $$$t$$$ without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as $$$s$$$ or as $$$t$$$.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — the number of locations and passages, respectively.Then $$$m$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) describing the endpoints of one of the passages.It is guaranteed that there is no pair of locations directly connected by two or more passages, and that any location is reachable from any other location.

Output: Print one integer — the maximum number of bosses your friend can place, considering all possible choices for $$$s$$$ and $$$t$$$.


Sample Inputs:
5 5
1 2
2 3
3 1
4 1
5 2

4 3
1 2
4 3
3 2

Sample Outputs:
2

3

Solution (Python):
import sys
input = sys.stdin.readline

def get_input():
    (n, m) = [int(x) for x in input().split(' ')]
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v) = [int(x) for x in input().split(' ')]
        graph[u].append(v)
        graph[v].append(u)
    return graph

def dfs_bridges(graph, node):
    n = len(graph)
    time = 0
    discover_time = [0] * n
    low = [0] * n
    pi = [None] * n
    color = ['white'] * n
    ecc = [-1] * n
    ecc_number = 0
    bridges = []
    stack = [node]
    discover_stack = []
    while stack:
        current_node = stack[-1]
        if color[current_node] != 'white':
            stack.pop()
            if color[current_node] == 'grey':
                if pi[current_node] is not None:
                    low[pi[current_node]] = min(low[pi[current_node]], low[current_node])
                    if low[current_node] == discover_time[current_node]:
                        bridges.append((pi[current_node], current_node))
                        while discover_stack:
                            top = discover_stack.pop()
                            ecc[top] = ecc_number
                            if top == current_node:
                                break
                        ecc_number += 1
                color[current_node] = 'black'
            continue
        time += 1
        color[current_node] = 'grey'
        low[current_node] = discover_time[current_node] = time
        discover_stack.append(current_node)
        for adj in graph[current_node]:
            if color[adj] == 'white':
                pi[adj] = current_node
                stack.append(adj)
            elif pi[current_node] != adj:
                low[current_node] = min(low[current_node], discover_time[adj])
    else:
        while discover_stack:
            top = discover_stack.pop()
            ecc[top] = ecc_number
        ecc_number += 1
    return (ecc_number, ecc, bridges)

def build_bridge_tree(ecc_count, ecc, bridges):
    n = len(graph)
    bridge_tree = [[] for _ in range(ecc_count)]
    for (u, v) in bridges:
        if ecc[u] != ecc[v]:
            bridge_tree[ecc[u]].append(ecc[v])
            bridge_tree[ecc[v]].append(ecc[u])
    return bridge_tree

def diameter(tree, root):
    n = len(tree)
    pi = [None] * n
    color = ['white'] * n
    (dp1, dp2) = ([0] * n, [0] * n)
    stack = [root]
    while stack:
        current_node = stack[-1]
        if color[current_node] != 'white':
            stack.pop()
            if color[current_node] == 'grey':
                parent = pi[current_node]
                if parent is not None:
                    t = dp1[current_node] + 1
                    if t > dp1[parent]:
                        (t, dp1[parent]) = (dp1[parent], t)
                    if t > dp2[parent]:
                        (t, dp2[parent]) = (dp2[parent], t)
                color[current_node] = 'black'
            continue
        color[current_node] = 'grey'
        for adj in tree[current_node]:
            if color[adj] == 'white':
                pi[adj] = current_node
                stack.append(adj)
    root = max(range(n), key=lambda x: dp1[x] + dp2[x])
    return dp1[root] + dp2[root]

def dfs_tree(tree, node):
    n = len(tree)
    visited = [False] * n
    distances = [0] * n
    current_distance = 0
    stack = [node]
    while stack:
        current_node = stack[-1]
        if visited[current_node]:
            stack.pop()
            current_distance -= 1
            continue
        visited[current_node] = True
        distances[current_node] = current_distance
        current_distance += 1
        for adj in tree[current_node]:
            if not visited[adj]:
                stack.append(adj)
    return distances
if __name__ == '__main__':
    graph = get_input()
    (ecc_count, ecc, bridges) = dfs_bridges(graph, 1)
    bridge_tree = build_bridge_tree(ecc_count, ecc, bridges)
    if ecc_count > 2:
        root = [x for (x, l) in enumerate(bridge_tree) if len(l) > 1][0]
        print(diameter(bridge_tree, root))
    else:
        print(ecc_count - 1)

Solution (Python):
import sys

def get_input():
    (n, m) = [int(x) for x in sys.stdin.readline().split(' ')]
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v) = [int(x) for x in sys.stdin.readline().split(' ')]
        graph[u].append(v)
        graph[v].append(u)
    return graph

def dfs_bridges(graph, node):
    n = len(graph)
    time = 0
    discover_time = [0] * n
    low = [0] * n
    pi = [None] * n
    color = ['white'] * n
    ecc = [-1] * n
    ecc_number = 0
    bridges = []
    stack = [node]
    discover_stack = []
    while stack:
        current_node = stack[-1]
        if color[current_node] != 'white':
            stack.pop()
            if color[current_node] == 'grey':
                if pi[current_node] is not None:
                    low[pi[current_node]] = min(low[pi[current_node]], low[current_node])
                    if low[current_node] == discover_time[current_node]:
                        bridges.append((pi[current_node], current_node))
                        while discover_stack:
                            top = discover_stack.pop()
                            ecc[top] = ecc_number
                            if top == current_node:
                                break
                        ecc_number += 1
                color[current_node] = 'black'
            continue
        time += 1
        color[current_node] = 'grey'
        low[current_node] = discover_time[current_node] = time
        discover_stack.append(current_node)
        for adj in graph[current_node]:
            if color[adj] == 'white':
                pi[adj] = current_node
                stack.append(adj)
            elif pi[current_node] != adj:
                low[current_node] = min(low[current_node], discover_time[adj])
    else:
        while discover_stack:
            top = discover_stack.pop()
            ecc[top] = ecc_number
        ecc_number += 1
    return (ecc_number, ecc, bridges)

def build_bridge_tree(ecc_count, ecc, bridges):
    n = len(graph)
    bridge_tree = [[] for _ in range(ecc_count)]
    for (u, v) in bridges:
        if ecc[u] != ecc[v]:
            bridge_tree[ecc[u]].append(ecc[v])
            bridge_tree[ecc[v]].append(ecc[u])
    return bridge_tree

def dfs_tree(tree, node):
    n = len(tree)
    visited = [False] * n
    distances = [0] * n
    current_distance = 0
    stack = [node]
    while stack:
        current_node = stack[-1]
        if visited[current_node]:
            stack.pop()
            current_distance -= 1
            continue
        visited[current_node] = True
        distances[current_node] = current_distance
        current_distance += 1
        for adj in tree[current_node]:
            if not visited[adj]:
                stack.append(adj)
    return distances

def diameter(tree):
    distances = dfs_tree(bridge_tree, 0)
    node = max(enumerate(distances), key=lambda t: t[1])[0]
    distances = dfs_tree(bridge_tree, node)
    return max(distances)
if __name__ == '__main__':
    graph = get_input()
    (ecc_count, ecc, bridges) = dfs_bridges(graph, 1)
    bridge_tree = build_bridge_tree(ecc_count, ecc, bridges)
    print(diameter(bridge_tree))

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

def lowlink():
    (o, parent, dist, B) = dfs(1)
    l = [n + 1] * (n + 1)
    for i in range(n + 1):
        l[i] = o[i]
    for i in range(1, n + 1):
        for j in B[i]:
            l[i] = min(l[i], l[j])
    x = [[] for _ in range(n + 2)]
    for i in range(1, n + 1):
        x[dist[i]].append(i)
    for i in range(n + 1, 0, -1):
        for j in x[i]:
            l[parent[j]] = min(l[parent[j]], l[j])
    return (o, l, parent, dist, B, x)

def dfs(s):
    st = [s]
    dist = [-1] * (n + 1)
    dist[s] = 0
    nowe = [0] * (n + 1)
    o = [-1] * (n + 1)
    o[s] = 0
    parent = [-1] * (n + 1)
    B = [[] for _ in range(n + 1)]
    t = 1
    while st:
        i = st[-1]
        Gi = G[i]
        nowei = nowe[i]
        while nowei < len(Gi):
            j = Gi[nowei]
            if dist[j] == -1:
                dist[j] = dist[i] + 1
                st.append(j)
                o[j] = t
                t += 1
                parent[j] = i
                break
            elif parent[j] ^ i:
                B[j].append(i)
            nowei += 1
        nowe[i] = nowei
        if nowe[i] == len(Gi):
            st.pop()
    return (o, parent, dist, B)

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    (ma, x) = (0, -1)
    while q:
        i = q.popleft()
        di = dist[i]
        if ma < di:
            (ma, x) = (di, i)
        for j in G[i]:
            if dist[j] == -1:
                q.append(j)
                if (i == parent[j] or j == parent[i]) and (o[i] < l[j] or o[j] < l[i]):
                    dist[j] = di + 1
                else:
                    dist[j] = di
    return (x, ma)
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    (x, y) = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
(o, l, parent, dist, B, x) = lowlink()
(m, _) = bfs(1)
(_, ans) = bfs(m)
print(ans)