unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1791: Find Center of Star Graph

link

In-degree

All edges of a star graph involves the center. Therefore, the center’s indegree = len(edges).

Time: \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        e = len(edges)
        n = e+1
        ind = [0] * (n+1)
        for u, v in edges:
            ind[u] += 1
            ind[v] += 1
        return next(u for u in range(1, n+1) if ind[u] == e)

Overlapping vertex

Any pair of edges must include the center. So, the center is the overlap between first two edges.

Time: \mathcal{O}(1), space: \mathcal{O}(1).

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if len(edges) == 1:
            u, v = edges[0]
            return u
        overlap = set(edges[0]) & set(edges[1])
        return next(u for u in overlap)

Or,

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if len(edges) == 1:
            u, v = edges[0]
            return u
        u, v = edges[0]
        return u if u in edges[1] else v

tanvirdotzaman

,

Leave a comment