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.
1public class Solution {
2 public int FindCenter(int[][] edges) {
3 int u1 = edges[0][0], v1 = edges[0][1];
4 int u2 = edges[1][0], v2 = edges[1][1];
5 if (u1 == u2 || u1 == v2) return u1;
6 return v1;
7 }
8}
9
The solution adopts a similar method using comparison amongst the initial nodes for the first two edges in C#.
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)
1#include <vector>
2#include <unordered_map>
using namespace std;
class Solution {
public:
int findCenter(vector<vector<int>>& edges) {
unordered_map<int, int> count;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
if (++count[u] > 1) return u;
if (++count[v] > 1) return v;
}
return -1; // Should never reach here
}
};
The C++ solution uses an unordered_map to tally the occurrence of each node. The first node reaching a count above 1 is the center.