题目
标题和出处
标题：找出星型图的中心结点
难度
3 级
题目描述
要求
有一个无向的星型图，由编号从 1 \texttt{1} 1 到 n \texttt{n} n 的 n \texttt{n} n 个结点组成。星型图有一个中心结点，并且恰有 n - 1 \texttt{n - 1} n - 1 条边将中心结点与其他每个结点相连。
给定一个二维整数数组 edges \texttt{edges} edges，其中 edges[i] = [u i , v i ] \texttt{edges[i] = [u}_\texttt{i}\texttt{, v}_\texttt{i}\texttt{]} edges[i] = [ui, vi] 表示在结点 u i \texttt{u}_\texttt{i} ui 和 v i \texttt{v}_\texttt{i} vi 之间存在一条边。返回给定的星型图的中心结点。
示例
示例 1：
输入： edges = [[1,2],[2,3],[4,2]] \texttt{edges = [[1,2],[2,3],[4,2]]} edges = [[1,2],[2,3],[4,2]]
输出： 2 \texttt{2} 2
解释：如上图所示，结点 2 \texttt{2} 2 与其他每个结点都相连，所以结点 2 \texttt{2} 2 是中心结点。
示例 2：
输入： edges = [[1,2],[5,1],[1,3],[1,4]] \texttt{edges = [[1,2],[5,1],[1,3],[1,4]]} edges = [[1,2],[5,1],[1,3],[1,4]]
输出： 1 \texttt{1} 1
数据范围
- 3 ≤ n ≤ 10 5 \texttt{3} \le \texttt{n} \le \texttt{10}^\texttt{5} 3≤n≤105
- edges.length = n − 1 \texttt{edges.length} = \texttt{n} - \texttt{1} edges.length=n−1
- edges[i].length = 2 \texttt{edges[i].length} = \texttt{2} edges[i].length=2
- 1 ≤ u i , v i ≤ n \texttt{1} \le \texttt{u}_\texttt{i}\texttt{, v}_\texttt{i} \le \texttt{n} 1≤ui, vi≤n
- u i ≠ v i \texttt{u}_\texttt{i} \ne \texttt{v}_\texttt{i} ui=vi
- 给定的 edges \texttt{edges} edges 表示一个有效的星型图
解法一
思路和算法
星型图是无向图，有 n n n 个结点，中心结点和其余 n − 1 n - 1 n−1 个结点都相连，其余结点都只和中心结点相连。因此，中心结点的度是 n − 1 n - 1 n−1，其余结点的度都是 1 1 1。
遍历星型图中的边，得到每个结点的度，然后遍历每个结点，找到度是 n − 1 n - 1 n−1 的结点，该结点即为星型图的中心结点。
代码
class Solution {
public int findCenter(int[][] edges) {
int n = edges.length + 1;
int[] degrees = new int[n + 1];
for (int[] edge : edges) {
degrees[edge[0]]++;
degrees[edge[1]]++;
}
int center = 0;
for (int i = 1; i <= n; i++) {
if (degrees[i] == n - 1) {
center = i;
break;
}
}
return center;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是星型图的结点数。需要遍历星型图的每条边计算每个结点的度，然后遍历每个结点得到星型图的中心结点。由于星型图有 n − 1 n - 1 n−1 条边，因此时间复杂度是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是星型图的结点数。需要记录每个结点的度。
解法二
思路和算法
由于星型图的中心结点和其余 n − 1 n - 1 n−1 个结点都相连，其余结点都只和中心结点相连，因此中心结点一定在每条边中都出现，其余每个结点都只在一条边中出现，每条边中的两个结点一定有一个是中心结点。
利用星型图的上述性质，只要任选星型图中的两条边，寻找同时在这两条边中出现的结点，该结点即为星型图的中心结点。
具体做法是，选 edges [ 0 ] \textit{edges}[0] edges[0] 和 edges [ 1 ] \textit{edges}[1] edges[1]，判断 edges [ 0 ] [ 0 ] \textit{edges}[0][0] edges[0][0] 是否在 edges [ 1 ] \textit{edges}[1] edges[1] 中出现，如果出现则 edges [ 0 ] [ 0 ] \textit{edges}[0][0] edges[0][0] 是星型图的中心结点，否则 edges [ 0 ] [ 1 ] \textit{edges}[0][1] edges[0][1] 是星型图的中心结点。
代码
class Solution {
public int findCenter(int[][] edges) {
return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
}
}
复杂度分析
-
时间复杂度： O ( 1 ) O(1) O(1)。
-
空间复杂度： O ( 1 ) O(1) O(1)。