# Find Center of Star Graph
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-center-of-star-graph)
Canonical: https://scaleengineer.com/dsa/problems/find-center-of-star-graph
**Data structures:** Graph
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/find-center-of-star-graph/image0.png) 

**Input:** edges = [[1,2],[2,3],[4,2]]
**Output:** 2
**Explanation:** As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

**Example 2:**

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

**Constraints:**

* `3 <= n <= 105`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `1 <= ui, vi <= n`
* `ui != vi`
* The given `edges` represent a valid star graph.

# Approaches
## Degree Counting
This approach is based on the property that the center node of a star graph has a degree of `n-1`, while all other nodes have a degree of 1. We can count the degree of each node by iterating through all the edges. The node with the highest degree is the center.
**Time:** O(N), where N is the number of nodes. We iterate through N-1 edges to populate the degree counts, and then iterate through up to N nodes to find the center. This results in a linear time complexity. · **Space:** O(N), where N is the number of nodes. We use an auxiliary array of size N+1 to store the degree of each node.
**Pros:** It's a general approach that can find the node with the highest degree in any graph.; The logic is straightforward and easy to understand.
**Cons:** It's not the most efficient solution for this specific problem, as it requires O(N) time and space.; It processes the entire input, which is unnecessary given the problem's guarantees.
### Explanation
In a star graph with `n` nodes, the center node is connected to all other `n-1` nodes. This means its degree (the number of edges connected to it) is `n-1`. All other nodes (the 'spokes' of the star) are only connected to the center, so their degree is 1.

We can use this property to find the center. The algorithm involves two main steps:
1.  **Count Degrees:** We iterate through the `edges` array. For each edge `[u, v]`, we increment the degree count for both node `u` and node `v`. A hash map or an array can be used to store these counts. Since node labels are from 1 to `n`, an array of size `n+1` is a simple choice.
2.  **Find Center:** After counting, we iterate through our degree counts. The node whose degree is `n-1` (or simply the maximum degree) is the center of the star graph.

For example, given `edges = [[1,2],[2,3],[4,2]]`, there are `n = 4` nodes. The center must have a degree of 3.
After processing all edges, the degrees would be: `degree(1)=1`, `degree(2)=3`, `degree(3)=1`, `degree(4)=1`.
Clearly, node 2 has a degree of 3, making it the center.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findCenter(int[][] edges) {
        int n = edges.length + 1;
        int[] degree = new int[n + 1];
        
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (degree[i] == n - 1) {
                return i;
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
- 1. Determine the number of nodes, `n`, which is `edges.length + 1`.
- 2. Create an integer array `degree` of size `n + 1` to store the degree of each node, initialized to zeros.
- 3. Iterate through each `edge` in the `edges` array.
- 4. For each `edge = [u, v]`, increment `degree[u]` and `degree[v]`.
- 5. After iterating through all edges, loop from `i = 1` to `n`.
- 6. If `degree[i]` is equal to `n - 1`, then `i` is the center node. Return `i`.

## Constant Time Check of First Two Edges
This highly efficient approach leverages the core property of a star graph: the center node must be a part of every edge. Therefore, the center node must be the common node present in any two edges. By simply inspecting the first two edges, we can identify the center in constant time.
**Time:** O(1). The solution only accesses the first two elements of the `edges` array and performs a constant number of comparisons, regardless of the size of the input. · **Space:** O(1). No extra space is used that scales with the input size.
**Pros:** Extremely fast and memory-efficient.; Very simple and concise implementation.
**Cons:** This solution is highly specialized and only works because the input is guaranteed to be a valid star graph.; It would fail on a general graph or if the input did not represent a star graph.
### Explanation
The problem guarantees that the input graph is a valid star graph. In a star graph, there is a central node connected to all other `n-1` nodes. This implies that the center node must appear in every single one of the `n-1` edges.

Based on this insight, we don't need to examine all the edges. We only need to look at any two distinct edges to find the node they have in common. The simplest choice is to use the first two edges: `edges[0]` and `edges[1]`.

Let `edges[0] = [u, v]` and `edges[1] = [x, y]`. The center node must be one of the nodes in the first edge, i.e., either `u` or `v`. We can check which of these two also appears in the second edge.
- If `u` is equal to `x` or `y`, then `u` is the center.
- Otherwise, `v` must be the center (since a center is guaranteed to exist and be common to both edges).

This check involves a maximum of two comparisons and is independent of the number of nodes `n`.

```java
class Solution {
    public int findCenter(int[][] edges) {
        // The center node must be in the first edge.
        int node1 = edges[0][0];
        int node2 = edges[0][1];
        
        // The center node must also be in the second edge.
        // So we check which of node1 or node2 is in the second edge.
        if (node1 == edges[1][0] || node1 == edges[1][1]) {
            return node1;
        } else {
            return node2;
        }
    }
}
```
### Algorithm
- 1. Consider the first edge, `edges[0]`, which contains two nodes, let's call them `candidate1` and `candidate2`.
- 2. Consider the second edge, `edges[1]`.
- 3. Check if `candidate1` is present in `edges[1]`.
- 4. If it is, `candidate1` is the center. Return `candidate1`.
- 5. If not, `candidate2` must be the center (due to the star graph property). Return `candidate2`.

# Solutions
### Java

```java
class Solution {
public
  int findCenter(int[][] edges) {
    int a = edges[0][0], b = edges[0][1];
    int c = edges[1][0], d = edges[1][1];
    return a == c || a == d ? a : b;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} edges * @return {number} */ var findCenter =
  function (edges) {
    const [a, b] = edges[0];
    const [c, d] = edges[1];
    return a == c || a == d ? a : b;
  };

```

### CPP

```cpp
class Solution {
public:
  int findCenter(vector<vector<int>> &edges) {
    int a = edges[0][0], b = edges[0][1];
    int c = edges[1][0], d = edges[1][1];
    return a == c || a == d ? a : b;
  }
};

```

### Python

```python
class Solution:
    def findCenter(
        self, edges: List[List[int]]) -> int: return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

```