發表新討論
#50815: 關節點 DFS


xutingyao0505@gmail.com (TingYao Xu)

學校 : 不指定學校
編號 : 314841
來源 : [27.240.209.167]
最後登入時間 ：
2025-08-12 14:36:50
a257. NCPC2011 Problem K Key Persons -- NCPC 2011
| From: [27.240.209.167] | 發表日期: 2025-08-12 14:37
import sys
import math

def solve():
    """
    解決「關鍵人」問題。
    此函數會讀取多個測試案例，並對每個案例找出關鍵人的數量。
    一個關鍵人是一個「關節點」(articulation point)，
    其移除會增加圖中連通分量的數量。
    """
   
    # 這是用於尋找關節點的 DFS 演算法
    # 'time' 是一個 mutable list，用於在遞歸調用中共享和更新時間戳。
    def find_articulation_points_dfs(u, adj, discovery_time, low_link, parent, articulation_points, time):
        # 標記當前節點為已訪問，並設置其發現時間和最低連結值
        discovery_time[u] = low_link[u] = time[0]
        time[0] += 1
       
        children = 0  # 記錄 DFS 樹中 u 的子節點數
       
        # 遍歷所有與 u 相鄰的節點 v
        for v in adj[u]:
            # 如果 v 是 u 的父節點，則跳過
            if v == parent[u]:
                continue
           
            # 如果 v 已被訪問，說明存在一個後向邊 (back edge)
            if discovery_time[v] != -1:
                # 更新 u 的最低連結值
                low_link[u] = min(low_link[u], discovery_time[v])
            else:
                # 否則，v 是 u 的一個新子節點，進行遞歸調用
                children += 1
                parent[v] = u
                find_articulation_points_dfs(v, adj, discovery_time, low_link, parent, articulation_points, time)
               
                # 更新 u 的最低連結值為其子節點中最低連結值中最小的
                low_link[u] = min(low_link[u], low_link[v])
               
                # 檢查 u 是否為關節點
                # 情況 1: u 是 DFS 樹的根節點，且有超過一個子節點
                if parent[u] == -1 and children > 1:
                    articulation_points[u] = True
               
                # 情況 2: u 不是根節點，且其某個子節點 v 的 low_link 值大於或等於 u 的發現時間
                # 這表示 v 無法從其子樹中找到回到 u 或 u 的祖先節點的後向邊，
                # 因此移除 u 會將 v 的子樹與圖的其餘部分分離。
                if parent[u] != -1 and low_link[v] >= discovery_time[u]:
                    articulation_points[u] = True

    try:
        # 讀取測試案例的數量
        t_str = sys.stdin.readline()
        if not t_str: return
        t = int(t_str)

        for _ in range(t):
            # 讀取學生數量 n
            n_str = sys.stdin.readline()
            if not n_str: return
            n = int(n_str)
           
            # 讀取學生 ID
            students = []
            for _ in range(n):
                students.append(int(sys.stdin.readline()))
           
            # 處理 n <= 2 的特殊情況，此時不可能有關節點
            if n <= 2:
                print(0)
                continue

            # 構建圖的鄰接列表
            adj = [[] for _ in range(n)]
            for i in range(n):
                for j in range(i + 1, n):
                    # 如果兩個 ID 的最大公因數大於 1，則它們之間有邊
                    if math.gcd(students[i], students[j]) > 1:
                        adj[i].append(j)
                        adj[j].append(i)

            # 初始化尋找關節點所需的資料結構
            discovery_time = [-1] * n
            low_link = [-1] * n
            parent = [-1] * n
            articulation_points = [False] * n
            time = [0]
           
            # 遍歷所有節點，以處理可能存在的非連通圖
            for i in range(n):
                if discovery_time[i] == -1:
                    find_articulation_points_dfs(i, adj, discovery_time, low_link, parent, articulation_points, time)

            # 計算關節點的總數
            count = sum(articulation_points)
            print(count)

    except (IOError, ValueError) as e:
        # 處理可能的輸入錯誤
        print(f"An input error occurred: {e}", file=sys.stderr)

if __name__ == "__main__":
    solve()
ZeroJudge Forum