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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int findCenter(vector<vector<int>>& edges) {
7 int u1 = edges[0][0], v1 = edges[0][1];
8 int u2 = edges[1][0], v2 = edges[1][1];
9 if (u1 == u2 || u1 == v2) return u1;
10 else return v1;
11 }
12};
13
Similarly to the C solution, this approach also checks for repeating nodes in the first two edges to identify 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)
1var
JavaScript uses an object to determine the frequency and identifies the center upon the first re-occurrence.