找出星型图的中心节点 图解题解

这道题到底在问什么

输入

edges=[[1,2],[2,3],[4,2]]

输出

2

输入

edges=[[1,2],[5,1],[1,3],[1,4]]

输出

1

最优解：一步一步想明白

1. 3记牢这条主线:中心出现在每一条边里,叶子只出现在一条边里。所以中心必然同时躺在前两条边里,取这两条边的公共节点即可。下面先用最朴素的数度数法把这个直觉验一遍,再落到只看两条边的写法。
2. 4先用笨办法:数每个节点连了几条边(度数)舞台上是 5 个节点,编号 1 到 5,中间的连线就是边。先亮个谜底:这张图的中心是节点 1,等会儿一步步验。第一种最朴素的想法是数度数,也就是每个节点连了几条边。开始时所有度数都是 0,接下来扫每条边,给它的两个端点各加 1。
3. 5这条边连着节点 1 和 2,准备给两头各加 1看第 1 条边 [1, 2]。高亮的就是眼下这条边,它连着节点 1 和节点 2。数度数很机械,一条边给它的两个端点各记一笔。
4. 6节点 1:1,节点 2:1两头各加 1:节点 1 的度数变成 1,节点 2 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。
5. 7这条边连着节点 5 和 1,准备给两头各加 1看第 2 条边 [5, 1]。高亮的就是眼下这条边,它连着节点 5 和节点 1。数度数很机械,一条边给它的两个端点各记一笔。
6. 8节点 5:1,节点 1:2两头各加 1:节点 5 的度数变成 1,节点 1 的度数变成 2。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。
7. 9这条边连着节点 1 和 3,准备给两头各加 1看第 3 条边 [1, 3]。高亮的就是眼下这条边,它连着节点 1 和节点 3。数度数很机械,一条边给它的两个端点各记一笔。
8. 10节点 1:3,节点 3:1两头各加 1:节点 1 的度数变成 3,节点 3 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。
9. 11这条边连着节点 1 和 4,准备给两头各加 1看第 4 条边 [1, 4]。高亮的就是眼下这条边,它连着节点 1 和节点 4。数度数很机械,一条边给它的两个端点各记一笔。
10. 12节点 1:4,节点 4:1两头各加 1:节点 1 的度数变成 4,节点 4 的度数变成 1。你会注意到节点 1 每条边几乎都掺一脚,度数涨得最快,这正是中心的特征。
11. 13节点 1 度数 4,其余节点度数都是 14 条边全数完了。节点 1 的度数是 4,正好等于 n-1,也就是 5 减 1;其余 4 个节点度数都是 1。度数最高、达到 n-1 的那个就是中心。数度数这条路走得通,但它把每条边都扫了一遍,做了 O(边数) 的功。
12. 14叶子只连中心这一条边,中心连着所有叶子停下来品一下这个结构:每个叶子节点只连着中心一条边,所以度数都是 1,只在一条边里露过面;而中心连着全部 4 个叶子,出现在每一条边里。这个「中心出现在每条边、叶子只在一条边」的差别,就是下面把复杂度砍到 O(1) 的钥匙。
13. 15中心出现在每条边里 → 它一定在前两条边里既然中心出现在每一条边里,那它必然同时出现在最前面的两条边里。反过来,任何叶子只出现在一条边里,不可能既在第一条边又在第二条边。所以第一条边和第二条边的公共节点,只可能是中心。我们连后面的边都不用看了,只盯前两条。
14. 16中心必在这条边里:要么 1,要么 2拿出第一条边 edges[0] = [1, 2]。中心既然出现在每条边里,当然也在这条边里,所以中心只可能是 1 或者 2 这两个候选之一。现在还不知道是哪个,得靠第二条边来裁决。
15. 17中心也必在这条边里:要么 5,要么 1再看第二条边 edges[1] = [5, 1]。中心同样出现在这条边里,所以它也得是 5 或者 1。把两条边一对照,能同时出现在两条边里的,只有节点 1。这就是我们要找的公共节点。
16. 18比较:1 是不是 edges[1] 的端点具体怎么落到代码:取第一条边的第一个节点 edges[0][0] = 1,去第二条边 [5, 1] 里看它在不在。先跟第二条边的第一个端点 5 比,1 不等于 5,先不下结论,再看另一个端点。
17. 191 等于 edges[1] 的第二个端点,公共节点确定为 1再拿 1 跟第二条边的第二个端点比,1 正好等于 1,命中。这说明节点 1 同时出现在前两条边里,它就是那个公共节点,也就是中心。答案锁定为 1,跟开头亮的谜底对上了。
18. 20那答案就是 edges[0][1],另一个端点顺手想想反面情况。如果 edges[0][0] 没在第二条边里出现,说明它只在第一条边露过面,是个叶子,那中心就只能是第一条边的另一个端点 edges[0][1]。代码里就是一个三目:在就取第一个,不在就取第二个。
19. 21节点 2 只出现在第一条边里,是叶子看节点 2,它只在第一条边 [1, 2] 里出现过,第二条边里根本没有它。中心得连着 n-1 条边、出现在每一条边里,而 2 只连着一条边,度数是 1,注定是叶子,不可能当中心。这就从反面印证了公共节点法为什么可靠。
20. 22中心出现次数 = n-1 ≥ 2,叶子出现次数 = 1把道理收成一句:因为 n ≥ 3,星型图至少有 2 条边,中心出现在每一条边里,所以它一定同时在 edges[0] 和 edges[1] 里;而叶子只出现在一条边里,不可能横跨前两条边。于是前两条边唯一的公共节点必然是中心,看这两条边就足够了。
21. 23数度数法与两条边法,都指向节点 1两条路对照一下:数度数法扫完 4 条边,找出度数 4 的节点 1;两条边法只看前两条边,取公共点也是 1。结论完全一致,但后者只碰了两条边,做的是常数次比较,这就是我们最终要交的解法。
22. 24最终答案:中心节点 = 1整道题回放一遍:星型图的中心连着每个节点,出现在每一条边里。我们只取前两条边 [1, 2] 和 [5, 1],找它们的公共节点,得到 1,直接返回。一次比较搞定,这就是找星型图中心最省事的办法。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return a == c || a == d ? a : b;
    }
};

import java.util.*;
class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return a == c || a == d ? a : b;
    }
}

复杂度

面试官可能追问