L1-020 帅到没朋友python

### 关于 L1-020 “帅到没朋友”的解题思路 对于题目 **L1-020 ‘帅到没朋友’** 的描述，通常涉及社交关系中的连通性分析。这类问题的核心在于通过图论方法解决节点之间的连接情况。以下是基于 Python 实现该类问题的一种通用解决方案。 #### 图的表示与遍历 此类问题可以建模为无向图上的连通分量计算。具体来说，每个人视为一个节点，如果两个人之间有联系，则在对应的两个节点间建立一条边。最终目标是找到孤立节点的数量或特定条件下的子图数量。 一种常见的实现方式如下： ```python from collections import defaultdict def find_standalone_friends(friendships, n): """ 找出没有朋友的人数。 :param friendships: List[List[int]], 表示好友关系的二维数组 :param n: int, 总人数 :return: int, 孤立个体的数量 """ graph = defaultdict(list) visited = set() # 构造邻接表 for u, v in friendships: graph[u].append(v) graph[v].append(u) standalone_count = 0 def dfs(node): stack = [node] while stack: current_node = stack.pop() if current_node not in visited: visited.add(current_node) for neighbor in graph[current_node]: if neighbor not in visited: stack.append(neighbor) # 对每个未访问过的节点执行 DFS for person in range(n): if person not in visited and (not graph[person]): standalone_count += 1 elif person not in visited: dfs(person) return standalone_count ``` 上述代码实现了深度优先搜索（DFS），用于检测哪些人没有任何朋友关系[^3]。`friendships` 是输入的好友关系列表，而 `n` 则代表总人数。 --- #### 并查集优化方案 另一种高效的方法是利用并查集（Union-Find）来处理大规模数据的情况。这种方法能够快速判断任意两人是否属于同一个集合，并动态维护这些集合的关系。 ```python class UnionFind: def __init__(self, size): self.parent = list(range(size)) self.rank = [0] * size def find(self, p): """路径压缩""" if self.parent[p] != p: self.parent[p] = self.find(self.parent[p]) return self.parent[p] def union(self, p, q): root_p = self.find(p) root_q = self.find(q) if root_p != root_q: if self.rank[root_p] < self.rank[root_q]: self.parent[root_p] = root_q elif self.rank[root_p] > self.rank[root_q]: self.parent[root_q] = root_p else: self.parent[root_q] = root_p self.rank[root_p] += 1 def count_isolated_people(friendships, n): uf = UnionFind(n) isolated_set = set(range(n)) for a, b in friendships: uf.union(a, b) isolated_set.discard(a) isolated_set.discard(b) roots = {uf.find(i) for i in range(n)} return len(isolated_set), len(roots) ``` 此代码片段定义了一个 `UnionFind` 类，用于管理每个人的所属组别。最后统计独立个体数目以及总的连通分量数目[^4]。 --- ### 结果解释 两种方法均能有效解决问题，但在实际应用中需考虑时间复杂度和空间消耗等因素。当数据规模较小时，推荐使用 DFS 方法；而对于更大范围的数据集，并查集则更为适用。 ---