Sponsored
Sponsored
This approach relies on the characteristic that in a star graph, the center node is connected to all other nodes, meaning it appears in every edge. By counting the occurrence of each node in the edges, the one that appears most frequently is the center node.
Time Complexity: O(1) since it only involves fixed operations.
Space Complexity: O(1) as no additional data structures are used.
1class Solution:
2 def findCenter(self, edges: List[List[int]]) -> int:
3 u1, v1 = edges[0]
4 u2, v2 = edges[1]
5 if u1 == u2 or u1 == v2:
6 return u1
7 return v1
8
In Python, by destructuring the first two edges, the solution checks which node is common between them to find the center.
This approach involves using a hashmap or an array to count the degree or frequency of nodes appearing in the edge list. The node with the maximum frequency of appearance will be the center node.
Time Complexity: O(n)
Space Complexity: O(n)
1using System.Collections.Generic;
public class Solution {
public int FindCenter(int[][] edges) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (!count.ContainsKey(u)) count[u] = 0;
if (++count[u] > 1) return u;
if (!count.ContainsKey(v)) count[v] = 0;
if (++count[v] > 1) return v;
}
return -1; // Should not be reached
}
}
Here, a dictionary serves to log frequency and determine the center as soon as a node frequency exceeds 1.