本文共 1825 字，大约阅读时间需要 6 分钟。

要解决这个问题，我们需要找到最小的k值，使得删除编号1到k的犯罪团伙后，剩下的犯罪集团中最大的子集团的危险程度不超过n/2。这个问题可以通过并查集（Union-Find）数据结构来高效解决。

方法思路

解决代码

import sys
sys.setrecursionlimit(1 << 25)
def main():
    n = int(sys.stdin.readline())
    parent = list(range(n + 1))
    size = [1] * (n + 1)
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    edges = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        parts = list(map(int, sys.stdin.readline().split()))
        k = parts[0]
        edges[i] = []
        for j in range(1, k + 1):
            edges[i].append(parts[j])
    k_found = n
    for i in range(n, 0, -1):
        for j in edges[i]:
            if j > i:
                root_j = find(j)
                root_i = find(i)
                if root_j != root_i:
                    if size[root_j] > n // 2:
                        print(i)
                        return
                    parent[root_i] = root_j
                    size[root_j] += size[root_i]
                    if size[root_j] > n // 2:
                        print(i)
                        return
    print(n)
if __name__ == "__main__":
    main()

代码解释

这个方法确保了在处理过程中高效地管理连通性，并及时检查大小限制，保证了算法的正确性和高效性。