Find Center Of Star Graph - Leetcode Solution

Problem Statement: The problem states that given an undirected star graph with n edges, where in a star graph, there is one central vertex and n edges connected to n other vertices. We need to find the center of the given star graph. If the number of vertices in the star graph is even, then return -1.

Example:

Input: edges = [[1,2],[2,3],[3,4],[4,1]] Output: [2,3]

Solution: To solve this problem, we can follow the below steps:

1. Initialize two pointers, left and right.
2. Traverse the edges list and make a dictionary with all the vertices and how many times they occur in the edges list.
3. Now, iterate through the dictionary and for each key, check if its value is equal to n-1, where n is the total number of edges. If any key's value is equal to n-1, then that key is the center vertex of the star graph, and we return the key.
4. If no such key is found, we return -1.

Detailed Explanation of the Solution:

Step 1: Create two pointers left and right, representing the range of vertices in the edges list. Initialize them to 1 and n-1, respectively, where n is the length of the edges list.

Step 2: Create a dictionary 'degree' and traverse the edges list. For each edge in the list, add the vertices to the dictionary, and increment their degree by 1.

Step 3: Iterate through the dictionary, and for each key, check if its degree is equal to the total number of edges (n). If it is, then that key is the center vertex, and we return it. If there are multiple keys with degree=n, we can return any of them (as the star graph has a single center).

Step 4: If no center vertex is found, return -1.

Let's look at the Python code implementation for the above algorithm:

Python Code:

class Solution: def findCenter(self, edges: List[List[int]]) -> int:

    # Step 1
    left, right = 1, len(edges)-1
    
    # Step 2
    degree = {}
    for u,v in edges:
        degree[u] = degree.get(u,0) + 1
        degree[v] = degree.get(v,0) + 1
    
    # Step 3
    for k,v in degree.items():
        if v == len(edges):
            return k
    
    # Step 4
    return -1

The time complexity of this algorithm is O(n), where n is the number of edges in the graph, as we traverse the edges list only once and iterate through all keys in the dictionary. The space complexity is also O(n), as we use a dictionary to store the vertices and their degree.

Sample Input and Output:

Input: edges = [[1,2],[2,3],[3,1],[4,1]] Output: 1

Input: edges = [[1,2],[2,3],[3,4],[4,1]] Output: 2 or 3 (both are correct solutions)

Input: edges = [[1,5],[2,5],[3,5],[4,5]] Output: 5

Input: edges = [[1,2],[1,3],[1,4],[2,4]] Output: -1 (as the number of vertices is even, so there is no center vertex)

Thus, the solution to the given problem is to traverse the edges list, create a dictionary of all vertices and their degree, and return the key (vertex) with degree equal to the number of edges (n), which will be the center of the star graph.

1