Click here to Skip to main content
15,883,705 members
Please Sign up or sign in to vote.
4.00/5 (1 vote)
See more:
There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node. You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.
Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

What I have tried:

I have tried to count the frequency of each element and whosr frequency count equals n-1 return that value because there is only one node which has n-1 edges. The logic seems to be fine but I'm having problem in implementation part and I'm getting runtime error. Here is what I code -

int findCenter(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int>ans(n);
        for(int i=0;i<n;i++){
            int a = edges[i][0];
            int b = edges[i][1];
            ans[a]++;
            ans[b]++;
           
        }
        for(int i=0;i<n;i++){
            if(ans[i] > 1){
                return i+1;
            }
        }
        return -1;
    }


When I debug the code I'm getting runtime error bcz of these 2 lines-
ans[a]++ and ans[b]++.
I don't know what is wrong with these two lines but when I comment these 2 lines I don't have any runtime error although the output is incorrect
Posted
Updated 15-Jun-21 21:20pm

1 solution

Quote:
When I debug the code I'm getting runtime error bcz of these 2 lines-ans[a]++ and ans[b]++.

Try
C++
ans[a-1]++;
ans[b-1]++;

In C++, arrays and vectors are 0 based: a vector of size n goes from 0 to n-1.
Nodes in your graph goes from 1 to n.
Beware, here, n is number of nodes, not number of edges.
 
Share this answer
 
v3
Comments
Peter_in_2780 16-Jun-21 3:52am    
That won't work either. You'll still be one off the end.
The number of nodes is ONE GREATER than the number of edges.
Patrice T 16-Jun-21 4:01am    
Ok.
Did checked that OP counted nodes instead of edges.
Priyanka Somani 16-Jun-21 4:08am    
This won't work as I had already checked by debugging the code with cout statements. The only problem is with these 2 lines. It's a leetcode question and you can find these question there easily
Priyanka Somani 16-Jun-21 13:13pm    
Any update what's the error. I'm still not getting it.
Patrice T 16-Jun-21 14:15pm    
Update is "Beware, here, n is number of nodes, not number of edges."

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900