Problem link ও উৎস
- **Original source:** Classic graph representation warm-up
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Easy
- **Pattern:** representation warm-up (degree / adjacency reasoning)
- **Basic idea inherited from:** adjacency আর degree counting (দেখো [../concept.md](../concept.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **star graph** দেওয়া আছে — মানে এমন একটা graph, যেখানে একটা মাঝখানের node (center) বাকি প্রতিটা node-এর সাথে সরাসরি যুক্ত, আর center ছাড়া আর কোনো দুটো node-এর মধ্যে কোনো edge নেই। `n` টা node হলে edge থাকে ঠিক `n - 1` টা। তোমাকে `edges` list টা দেওয়া হবে; খুঁজে বের করো কোন node টা center।
```text
2
|
1 -- 2 -- 3 <- এখানে 2 হলো center
|
4
```
### Input ও output {#8-example-input-and-output}
```text
Input : edges = [[1,2],[2,3],[4,2]]
Output: 2
Input : edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
Edge case (সবচেয়ে ছোট star, 3 node): edges = [[1,2],[2,3]] -> 2
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা সাইকেলের চাকা ভাবো। মাঝখানের hub থেকে প্রতিটা spoke বাইরের rim-এর দিকে যায়। তুমি যদি যেকোনো দুটো spoke ধরো, দুটোই কোথায় মেলে? hub-এ। ঠিক তেমনি, star graph-এর যেকোনো দুটো edge ধরলে তারা center-এ মেলে। চাকার hub-ই হলো graph-এর center।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **degree** আর **adjacency** বোঝা ([../concept.md](../concept.md))। একটা node-এর degree মানে কয়টা edge তাকে ছোঁয়। Star graph-এ center-এর degree সবচেয়ে বেশি — সে সবার সাথে যুক্ত, তাই তার degree `n - 1`। বাকি প্রতিটা node শুধু center-কে ছোঁয়, তাই তাদের degree 1। এটাই পুরো problem-টার চাবি।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা ছোট গোনার সত্য: star graph-এ **center প্রতিটা edge-এ থাকে**। কারণ প্রতিটা edge-এর এক প্রান্ত সবসময় center। তাই যেকোনো দুটো edge নাও — center দুটোতেই common থাকবে। প্রথম দুই edge-এর মধ্যে যে node-টা দুজায়গাতেই দেখা যায়, সেটাই center। দুটো edge-ই যথেষ্ট, পুরো list পড়ার দরকার নেই।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুই রকম পথ আছে:
- **Degree count** — একটা dict-এ প্রতিটা node কতবার edge-এ এল গোনো; degree `n - 1`-ওয়ালা node-টাই center। এটা adjacency বানানোরই হালকা version।
- **শুধু দুটো edge** — কোনো extra structure ছাড়াই, প্রথম দুই edge-এর common node বের করো। O(1) space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Degree count fit করে কারণ "কে সবার সাথে যুক্ত" প্রশ্নটা আসলে "কার degree সবচেয়ে বড়" — আর সেটা গোনাই degree count-এর কাজ। আর দুই-edge trick fit করে কারণ star graph-এর গঠনটাই এত কড়া যে পুরো তথ্য মাত্র দুটো edge-এই লুকিয়ে আছে — বাকিটা পড়া শুধু সময় নষ্ট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা node-এর degree গোনো একটা dict-এ। সব edge ঘুরে দুই প্রান্তের count বাড়াও, তারপর যে node-এর count `n - 1`, সেটাই center।
```text
1) সব edge পড়ো, degree[u] += 1, degree[v] += 1
2) n = edge সংখ্যা + 1
3) degree == n-1 যে node-এ, return করো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Degree count ভুল কিছু না — O(E) time, কাজ করে। কিন্তু এটা **অপ্রয়োজনীয় কাজ**: পুরো edge list পড়তে হয়, অথচ star graph-এর গঠন এত সরল যে উত্তর প্রথম দুই edge-এই বসে আছে। Interview-তে এটাই দেখার বিষয় — তুমি কি structure-টা কাজে লাগিয়ে O(1)-এ নামতে পারো।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **center প্রতিটা edge-এ উপস্থিত।** তাই প্রথম edge-এর দুটো node-এর একটা center; কোনটা, সেটা দ্বিতীয় edge দেখলেই বোঝা যায়। প্রথম edge-এর যে node-টা দ্বিতীয় edge-এও আছে, সেটাই center।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`edges[0]` থেকে দুটো candidate পেলে — `a` আর `b`। এখন `edges[1]` দেখো। যদি `a` সেখানে থাকে, center হলো `a`; নাহলে center হলো `b`। ব্যস, দুটো edge পড়েই শেষ — O(1) time, O(1) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব edge ঘুরে সবচেয়ে যুক্ত node খুঁজব" না ভেবে ভাবো "center তো প্রতিটা edge-এ আছেই — তাহলে মাত্র দুটো edge-এর common জনই center।" বড় গোনার কাজটা একটা ছোট intersection-এ মিলিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`edges = [[1,2],[2,3],[4,2]]` দিয়ে দেখি:
```text
edge[0] = (1, 2) node 1, node 2
edge[1] = (2, 3) node 2, node 3
কোন node দুটো edge-এই আছে?
1 কি edge[1]-এ আছে? না।
2 কি edge[1]-এ আছে? হ্যাঁ! -> center = 2
degree দিয়ে যাচাই:
1: 1 বার (edge 1-2)
2: 3 বার (1-2, 2-3, 4-2) <- n-1 = 3, center
3: 1 বার
4: 1 বার
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `edges = [[1,2],[2,3],[4,2]]`:
1. `a, b = edges[0]` → `a = 1`, `b = 2`
2. `c, d = edges[1]` → `c = 2`, `d = 3`
3. `a (=1)` কি `(c, d) = (2, 3)`-এ আছে? না।
4. তাই center = `b` = `2`। return `2`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
def find_center(edges):
# star graph-এ center প্রথম দুই edge-এই common
a, b = edges[0]
c, d = edges[1]
return a if a in (c, d) else b
def find_center_by_degree(edges):
# degree count = adjacency list বানানোরই হালকা version
deg = defaultdict(int)
for u, v in edges:
deg[u] += 1
deg[v] += 1
n = len(edges) + 1 # n node, n-1 edge
for node, d in deg.items():
if d == n - 1: # center সবার সাথে যুক্ত
return node
return -1
# ---- tests ----
assert find_center([[1, 2], [2, 3], [4, 2]]) == 2
assert find_center([[1, 2], [5, 1], [1, 3], [1, 4]]) == 1
assert find_center([[1, 2], [2, 3]]) == 2 # সবচেয়ে ছোট star
assert find_center_by_degree([[1, 2], [2, 3], [4, 2]]) == 2
assert find_center_by_degree([[1, 2], [5, 1], [1, 3], [1, 4]]) == 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `a, b = edges[0]` — প্রথম edge-এর দুটো প্রান্ত, center এদেরই একজন।
- `c, d = edges[1]` — দ্বিতীয় edge-এর দুটো প্রান্ত।
- `return a if a in (c, d) else b` — `a` যদি দ্বিতীয় edge-এ থাকে, সে-ই center; নাহলে `b`।
- `find_center_by_degree`-এ `deg[u] += 1` / `deg[v] += 1` — প্রতিটা edge দুই node-এর degree বাড়ায়।
- `n = len(edges) + 1` — star graph-এ edge `n-1` টা, তাই node সংখ্যা edge + 1।
- `if d == n - 1` — degree `n-1`-ওয়ালা node-ই center।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`find_center([[1,2],[2,3],[4,2]])`: প্রথম edge `(1,2)`, দ্বিতীয় edge `(2,3)`। `1` দ্বিতীয় edge-এ নেই, তাই center = `2`। degree version-ও 2 দেয় (degree 3 = n-1)। সব assert pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
`find_center`: **O(1)** — শুধু দুটো edge পড়ে। `find_center_by_degree`: **O(E)** — সব edge একবার করে গোনে।
### অতিরিক্ত জায়গা {#19-space-complexity}
`find_center`: **O(1)** — কোনো extra structure নেই। `find_center_by_degree`: **O(V)** — degree dict-এ প্রতিটা node-এর জন্য একটা entry।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- পুরো edge list ঘুরে degree গোনা, যখন দুটো edge-ই যথেষ্ট — অপ্রয়োজনীয় O(E)।
- `a in (c, d)` লেখার বদলে ভুল করে `a == c` শুধু check করা — তাহলে center দ্বিতীয় edge-এর দ্বিতীয় প্রান্তে থাকলে miss হয়।
- node 1-indexed না 0-indexed, সেটা না খেয়াল করে degree version-এ `n` ভুল বার করা।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: graph representation — node, edge, degree, adjacency ([../concept.md](../concept.md))। এই problem-টা ওই vocabulary-র সবচেয়ে সহজ প্রয়োগ: শুধু degree-র গঠন বুঝলেই উত্তর। Traversal (BFS/DFS) এখানে দরকারই হয় না — তার আগে graph "পড়তে" শেখাই এই warm-up-এর উদ্দেশ্য।
### পরের অনুশীলন {#22-similar-harder-problems}
- Find if Path Exists in Graph (reachability) —