Viloyatlar soni

n ta shahar berilgan. isConnected nomli n × n matritsa shaharlar orasidagi to'g'ridan-to'g'ri ulanishni ko'rsatadi: isConnected[i][j] = 1 bo'lsa — i va j shaharlari bevosita ulangan, 0 bo'lsa — ulangan emas.

Bir-biriga to'g'ridan-to'g'ri yoki boshqa shaharlar orqali yetib borish mumkin bo'lgan shaharlar guruhi viloyat deyiladi.

Viloyatlar sonini toping.

Kirish:
  isConnected = [[1,1,0],
                 [1,1,0],
                 [0,0,1]]

Chiqish: 2

Shaharlar: 0, 1, 2. Shahar 0 va 1 bir-biriga ulangan — bir viloyat. Shahar 2 yakka — ikkinchi viloyat.

Kirish:
  isConnected = [[1,0,0],
                 [0,1,0],
                 [0,0,1]]

Chiqish: 3

Hech bir shahar boshqasiga ulanmagan — uchta alohida viloyat.

Kirish:
  isConnected = [[1,1,0],
                 [1,1,1],
                 [0,1,1]]

Chiqish: 1

0 ↔ 1 ↔ 2 — hammasi bitta viloyat.

Asosiy g'oya: connected componentlarni sanash

Bu masala — undirected grafda connected componentlar sonini topish.

isConnected matritsa adjacency matrix shaklida berilgan grafni ifodalaydi. Har katak (i, j) da 1 bo'lsa, i dan j ga va j dan i ga edge bor. 0 bo'lsa — edge yo'q. Diagonal isConnected[i][i] har doim 1 — shahar o'z-o'zi bilan ulangan (self-loop, traversalda e'tiborsiz qoldiriladi).

Yondashuv: 1. Har shahardan (vertex) boshlab, hali ko'rilmagan bo'lsa — yangi viloyat boshlanadi. 2. DFS yoki BFS bilan shu shahardan reachable barcha shaharlar visited belgilanadi. 3. Har yangi boshlanish viloyatlar sonini bir oshiradi.

DFS yondashuvi

FUNCTION FIND_CIRCLE_NUM(isConnected)
    n       = isConnected qatorlar soni
    visited = n ta FALSE qiymatdan iborat array
    count   = 0

    FOR i = 0 DAN n - 1 GACHA
        IF visited[i] = FALSE
            count = count + 1
            DFS(isConnected, visited, i)

    RETURN count

FUNCTION DFS(isConnected, visited, city)
    visited[city] = TRUE

    FOR j = 0 DAN n - 1 GACHA
        IF isConnected[city][j] = 1 VA visited[j] = FALSE
            DFS(isConnected, visited, j)

Adjacency list o'rniga adjacency matrix ishlatilganligi sababli j ning barcha 0..n-1 qiymatlarini ko'rib chiqish kerak. Adjacency matrix bilan DFS vaqt murakkabligi O(n²).

Bosqichma-bosqich dry run

isConnected = [[1,1,0],
               [1,1,1],
               [0,1,1]]

visited = [F, F, F],  count = 0

i=0: visited[0]=F → count = 1. DFS(0) boshlanadi:

DFS(0):
  visited[0] = TRUE
  j=0: isConnected[0][0]=1, visited[0]=TRUE → o'tkazib yuboriladi
  j=1: isConnected[0][1]=1, visited[1]=FALSE → DFS(1)
    DFS(1):
      visited[1] = TRUE
      j=0: isConnected[1][0]=1, visited[0]=TRUE → o'tkazib yuboriladi
      j=1: isConnected[1][1]=1, visited[1]=TRUE → o'tkazib yuboriladi
      j=2: isConnected[1][2]=1, visited[2]=FALSE → DFS(2)
        DFS(2):
          visited[2] = TRUE
          j=0: isConnected[2][0]=0 → o'tkazib yuboriladi
          j=1: isConnected[2][1]=1, visited[1]=TRUE → o'tkazib yuboriladi
          j=2: isConnected[2][2]=1, visited[2]=TRUE → o'tkazib yuboriladi
  j=2: isConnected[0][2]=0 → o'tkazib yuboriladi

DFS(0) tugadi. visited = [T, T, T].

i=1: visited[1]=TRUE → o'tkazib yuboriladi. i=2: visited[2]=TRUE → o'tkazib yuboriladi.

Javob: 1

---

Ikkinchi misol uchun dry run:

isConnected = [[1,1,0],
               [1,1,0],
               [0,0,1]]

visited = [F, F, F],  count = 0

i=0: DFS(0) → shahar 0 va 1 visited. count = 1. i=1: visited[1]=TRUE → o'tkazib yuboriladi. i=2: visited[2]=FALSE → count = 2. DFS(2) → faqat shahar 2 visited.

Javob: 2

BFS yondashuvi

FUNCTION FIND_CIRCLE_NUM_BFS(isConnected)
    n       = isConnected qatorlar soni
    visited = n ta FALSE qiymatdan iborat array
    count   = 0

    FOR i = 0 DAN n - 1 GACHA
        IF visited[i] = FALSE
            count = count + 1
            queue = [i]
            visited[i] = TRUE

            WHILE queue bo'sh emas
                city = queue.DEQUEUE()

                FOR j = 0 DAN n - 1 GACHA
                    IF isConnected[city][j] = 1 VA visited[j] = FALSE
                        visited[j] = TRUE
                        queue.ENQUEUE(j)

    RETURN count

BFS va DFS bu masalada bir xil natija beradi. Ikkalasi ham O(n²) vaqt va O(n) xotira oladi.

Vaqt va xotira murakkabligi

Xususiyat	Qiymat	Izoh
Vaqt	O(n²)	Har shahar uchun barcha n qator tekshiriladi
Xotira	O(n)	visited array va rekursiya/queue

Adjacency matrix berilgani sababli O(n²) vaqt muqarrar. Agar adjacency list shaklida berilsa, O(V + E) bo'lardi.

Edge case'lar

n = 1. Bitta shahar — bitta viloyat.

Barcha shaharlar alohida. Diagonal tashqarisida hamma 0 — n ta viloyat.

Barcha shaharlar ulangan. Hammasidan biriga yetib borish mumkin — 1 ta viloyat.

Diagonal qiymatlari. isConnected[i][i] = 1 har doim. DFS ichida j = city holati visited[city] = TRUE bo'lganligi sababli avtomatik o'tkazib yuboriladi.

Note

Bu masala "Number of Provinces" (LeetCode 547) nomi bilan ham tanilgan, avvalgi versiyasi "Friend Circles" deb atalgan. Ikkalasida ham bir xil mantiq — undirected grafda connected component sanash.

Alternativ yondashuv: Union-Find

Disconnected shaharlarni birlashtirish va viloyatlar sonini sanash uchun Union-Find (Disjoint Set Union) ham ishlatilishi mumkin:

FUNCTION FIND_CIRCLE_NUM_UNION_FIND(isConnected)
    n      = isConnected qatorlar soni
    parent = [0, 1, 2, ..., n-1]   // har shahar o'z ildizi
    count  = n                       // boshida n ta viloyat

    FUNCTION FIND(x)
        IF parent[x] ≠ x
            parent[x] = FIND(parent[x])   // path compression
        RETURN parent[x]

    FUNCTION UNION(x, y)
        rx = FIND(x)
        ry = FIND(y)
        IF rx ≠ ry
            parent[rx] = ry
            count = count - 1   // ikki viloyat birlashdi

    FOR i = 0 DAN n - 1 GACHA
        FOR j = i + 1 DAN n - 1 GACHA
            IF isConnected[i][j] = 1
                UNION(i, j)

    RETURN count

Union-Find bu masalada DFS/BFS bilan bir xil vaqt murakkabligini beradi, lekin dinamik ulanish qo'shilishida (online scenario) DFS/BFSdan samaraliroq bo'lishi mumkin.

Xulosa

Viloyatlar soni — adjacency matrix shaklida berilgan undirected grafda connected componentlarni sanash masalasi. DFS yoki BFS bilan har ko'rilmagan shaharchadan boshlab barcha ulangan shaharlar belgilanadi; har yangi boshlanish bir viloyatni ochadi.

Adjacency matrix sababli vaqt murakkabligi O(n²). Masala Union-Find bilan ham yechiladi — dinamik ulanish stsenariylarida Union-Find afzalroq.