Uol 2025 Wk3 && LeetCode Biweekly Contest 168 题解
Weak Vertices (弱顶点) 问题描述 在图论中，一个网络的结构强度通常可以通过识别其中的基本形状（如三角形）来分析。三角形能提供结构刚性，是许多应用中常见的母题。这个问题要求我们识别那些不属于任何三角形的顶点。一个顶点 i 被定义为属于一个三角形，如果它有两个不同的邻居 j 和 k，并且 j 和 k 彼此之间也是邻居。我们的任务是找出所有不满足此条件的顶点，问题将其称为“弱顶点”。图以邻接矩阵的形式给出。 我的代码 我的方法是对定义进行直接模拟。对每个顶点，我遍历其所有邻居对，并检查它们之间是否相连。 // 遍历从 0 到 n-1 的每个顶点 `i`，检查它是否是弱顶点。 for(int i=0; i<n; i++) { // 一个标志位，用于追踪顶点 `i` 是否属于任何三角形。 // 我们将其初始化为 true，假设 `i` 是弱顶点，直到找到反证。 bool flag = true; // 遍历 `i` 的所有邻居。 // 外层循环选择第一个邻居 `j`。 for(int j=0; j<siblings[i].size(); j++) { // 内层循环选择第二个邻居 `k`。 // 我们从 j+1 开始，以确保每对邻居只被考虑一次。 for(int k=j+1; k<siblings[i].size(); k++) { // 检查 `i` 的两个邻居，即 `siblings[i][j]` 和 `siblings[i][k]`， // 是否相互连接。 if(graph[siblings[i][j]][siblings[i][k]]) { // 如果它们相连，那么顶点 `i`、`j` 和 `k` 构成一个三角形。 // 因此，顶点 `i` 不是弱顶点。我们将标志位设为 false。 flag = false; // 既然已经找到了一个涉及 `i` 的三角形，我们可以停止对该顶点的检查。 break; } } // 如果标志位已被设为 false，我们也可以跳出外层的邻居循环。 if(!flag) { break; } } // 如果在检查完所有邻居对后，标志位仍然为 true， // 这意味着没有找到涉及 `i` 的三角形。因此，`i` 是一个弱顶点。 if(flag) { cout<<i<<' '; } } 我的解法及其正确性 这个问题要求我们识别给定无向图中所有不属于任何三角形的顶点。如果一个顶点满足这个条件，它就被认为是“弱”的。图的结构通过一个 $n \times n$ 的邻接矩阵给出，其中 $n$ 是顶点的数量。 ...