001 — Find Center of Star Graph¶

Source¶

Original source: Classic graph representation warm-up
Platform: LeetCode — https://leetcode.com/problems/find-center-of-star-graph/
Topic: graphs
Difficulty: Easy
Pattern: representation warm-up (degree / adjacency reasoning)
Basic idea inherited from: adjacency আর degree counting (দেখো ../concept.md)

1. Problem in simple words¶

তোমাকে একটা star graph দেওয়া আছে — মানে এমন একটা graph, যেখানে একটা মাঝখানের node (center) বাকি প্রতিটা node-এর সাথে সরাসরি যুক্ত, আর center ছাড়া আর কোনো দুটো node-এর মধ্যে কোনো edge নেই। n টা node হলে edge থাকে ঠিক n - 1 টা। তোমাকে edges list টা দেওয়া হবে; খুঁজে বের করো কোন node টা center।

        2
        |
   1 -- 2 -- 3      <- এখানে 2 হলো center
        |
        4

2. Which basic idea does this inherit from?¶

মূল ভিত হলো degree আর adjacency বোঝা (../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-এই লুকিয়ে আছে — বাকিটা পড়া শুধু সময় নষ্ট।

6. Real-life analogy¶

একটা সাইকেলের চাকা ভাবো। মাঝখানের hub থেকে প্রতিটা spoke বাইরের rim-এর দিকে যায়। তুমি যদি যেকোনো দুটো spoke ধরো, দুটোই কোথায় মেলে? hub-এ। ঠিক তেমনি, star graph-এর যেকোনো দুটো edge ধরলে তারা center-এ মেলে। চাকার hub-ই হলো graph-এর center।

7. Visual explanation¶

edges = [[1,2],[2,3],[4,2]] দিয়ে দেখি:

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 বার

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা node-এর degree গোনো একটা dict-এ। সব edge ঘুরে দুই প্রান্তের count বাড়াও, তারপর যে node-এর count n - 1, সেটাই center।

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-এ মিলিয়ে যায়।

14. Step-by-step dry run¶

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

a, b = edges[0] → a = 1, b = 2
c, d = edges[1] → c = 2, d = 3
a (=1) কি (c, d) = (2, 3)-এ আছে? না।
তাই center = b = 2। return 2।

15. Python solution¶

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।

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!।

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 ভুল বার করা।

21. Which basic problem this inherits from¶

ভিত্তি: graph representation — node, edge, degree, adjacency (../concept.md)। এই problem-টা ওই vocabulary-র সবচেয়ে সহজ প্রয়োগ: শুধু degree-র গঠন বুঝলেই উত্তর। Traversal (BFS/DFS) এখানে দরকারই হয় না — তার আগে graph "পড়তে" শেখাই এই warm-up-এর উদ্দেশ্য।

22. Similar harder problems¶

Find if Path Exists in Graph (reachability) — https://leetcode.com/problems/find-if-path-exists-in-graph/ (এই tracker-এর #2)
Number of Provinces (degree নয়, components) — https://leetcode.com/problems/number-of-provinces/ (#6)
Find the Town Judge (in/out degree reasoning) — https://leetcode.com/problems/find-the-town-judge/

23. Pattern learned¶

Representation warm-up: graph-এর গঠন (degree, adjacency) থেকেই অনেক সময় উত্তর সরাসরি বেরিয়ে আসে — traversal চালানোর আগে জিজ্ঞেস করো, "edge গুলোর গঠন কি একাই উত্তর দিয়ে দিচ্ছে?"

24. Final summary¶

ভবিষ্যতের আমাকে: "star graph-এর center প্রতিটা edge-এ আছে, তাই প্রথম দুই edge-এর common জনই center — O(1)।" যখনই 'এই node সবার সাথে যুক্ত' ধরনের গঠন দেখবে, degree-র কথা ভাববে, আর গঠনটা একাই উত্তর দিচ্ছে কিনা সবার আগে যাচাই করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।