1791-找出星型图的中心节点

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1
条边将中心节点与其他每个节点连接起来。

给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回
edges 所表示星型图的中心节点。

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2021/03/14/star_graph.png)

**输入：** edges = [[1,2],[2,3],[4,2]]
**输出：** 2
**解释：** 如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。

示例 2：

**输入：** edges = [[1,2],[5,1],[1,3],[1,4]]
**输出：** 1

提示：

  • 3 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • 题目数据给出的 edges 表示一个有效的星型图

方法一：计算每个节点的度

由 n 个节点组成的星型图中，有一个中心节点，有 n - 1 条边分别连接中心节点和其余的每个节点。因此，中心节点的度是 n - 1，其余每个节点的度都是 1。一个节点的度的含义是与该节点相连的边数。

遍历 edges 中的每条边并计算每个节点的度，度为 n - 1 的节点即为中心节点。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1
        degrees = [0] * (n + 1)
        for x, y in edges:
            degrees[x] += 1
            degrees[y] += 1
        for i, d in enumerate(degrees):
            if d == n - 1:
                return i
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]]++;
        }
        for (int i = 1; ; i++) {
            if (degrees[i] == n - 1) {
                return i;
            }
        }
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int FindCenter(int[][] edges) {
        int n = edges.Length + 1;
        int[] degrees = new int[n + 1];
        foreach (int[] edge in edges) {
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        for (int i = 1; ; i++) {
            if (degrees[i] == n - 1) {
                return i;
            }
        }
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<int> degrees(n + 1);
        for (auto & edge : edges) {
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        for (int i = 1; ; i++) {
            if (degrees[i] == n - 1) {
                return i;
            }
        }
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findCenter(int** edges, int edgesSize, int* edgesColSize){
    int n = edgesSize + 1;
    int * degrees = (int *)malloc(sizeof(int) * (n + 1));
    memset(degrees,0,sizeof(int) * (n + 1));
    for (int i = 0; i < edgesSize; i++) {
        degrees[edges[i][0]]++;
        degrees[edges[i][1]]++;
    }
    for (int i = 1; ; i++) {
        if (degrees[i] == n - 1) {
            free(degrees);
            return i;
        }
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var findCenter = function(edges) {
    const n = edges.length + 1;
    const degrees = new Array(n + 1).fill(0);
    for (const edge of edges) {
        degrees[edge[0]]++;
        degrees[edge[1]]++;
    }
    for (let i = 1; ; i++) {
        if (degrees[i] === n - 1) {
            return i;
        }
    }
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findCenter(edges [][]int) int {
    n := len(edges) + 1
    degrees := make([]int, n+1)
    for _, e := range edges {
        degrees[e[0]]++
        degrees[e[1]]++
    }
    for i, d := range degrees {
        if d == n-1 {
            return i
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是星型图中的节点数量。需要遍历 n - 1 条边计算每个节点的度，然后遍历 n 个节点寻找中心节点。

  • 空间复杂度：O(n)，其中 n 是星型图中的节点数量。需要创建数组存储每个节点的度。

方法二：寻找出现在两条边中的节点

由于只有星型图的中心节点的度是 n - 1，其余每个节点的度都是 1，因此只有星型图在所有的边中都出现，其余每个节点分别只在一条边中出现。

根据星型图的上述性质可知，对于星型图中的任意两条边，星型图的中心节点一定同时在这两条边中出现，其余节点一定不会同时在这两条边中出现。因此，可以任选两条边，然后寻找这两条边的公共节点，该节点即为星型图的中心节点。

具体做法是，选择 edges}[0] 和 edges}[1] 这两条边，则星型图的中心节点是 edges}[0][0] 或者 edges}[0][1]。如果 edges}[0][0] 和 edges}[1] 的两个节点之一相同则 edges}[0][0] 是星型图的中心节点，如果 edges}[0][0] 和 edges}[1] 的两个节点都不相同则 edges}[0][1] 是星型图的中心节点。

[sol2-Python3]
1
2
3
class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        return edges[0][0] if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1] else edges[0][1]
[sol2-Java]
1
2
3
4
5
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];
    }
}
[sol2-C#]
1
2
3
4
5
public 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];
    }
}
[sol2-C++]
1
2
3
4
5
6
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
    }
};
[sol2-C]
1
2
3
int findCenter(int** edges, int edgesSize, int* edgesColSize){
    return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
}
[sol2-JavaScript]
1
2
3
var findCenter = function(edges) {
    return edges[0][0] === edges[1][0] || edges[0][0] === edges[1][1] ? edges[0][0] : edges[0][1];
};
[sol2-Golang]
1
2
3
4
5
6
func findCenter(edges [][]int) int {
    if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
        return edges[0][0]
    }
    return edges[0][1]
}

复杂度分析

  • 时间复杂度：O(1)。

  • 空间复杂度：O(1)。

 Comments
On this page
1791-找出星型图的中心节点