Find Center of Star Graph

summary

• Finding the Center of a Star Graph

approach

• The solution iterates over each edge in the graph and increments the count of the nodes at each end of the edge
• It then checks if the count of any node exceeds 1
• If so, that node is the center of the star graph and the function returns it.

complexity

• O(n)

explain

• The time complexity of this solution is O(n) because in the worst case, we might have to iterate over all n edges
• The space complexity is also O(n) because in the worst case, we might have to store the count of all n nodes.

Solution Code:

class Solution {
public:
    int findCenter(vector>& edges) {
        int cnt[100001] = {0};
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            cnt[a]++;
            cnt[b]++;
            if (cnt[a] >= 2) return a;
            if (cnt[b] >= 2) return b;
        }
        return 0;
    }
};