Graflar

class MatritsaGraf:
    """Qo'shnilik matritsasi asosidagi graf."""

    def __init__(self, vershinalar):
        self.vershinalar = list(vershinalar)
        self._indeks = {v: i for i, v in enumerate(self.vershinalar)}
        n = len(self.vershinalar)
        self.matritsa = [[0] * n for _ in range(n)]

    def qirra_qosh(self, birinchi, ikkinchi, vazn=1):
        i, j = self._indeks[birinchi], self._indeks[ikkinchi]
        self.matritsa[i][j] = vazn
        self.matritsa[j][i] = vazn        # yo'naltirilmagan

    def bogliqmi(self, birinchi, ikkinchi):
        """O(1) - matritsaning kuchli tomoni."""
        return self.matritsa[self._indeks[birinchi]][self._indeks[ikkinchi]] != 0

    def qoshnilar(self, vershina):
        """O(n) - butun qatorni ko'rish kerak."""
        i = self._indeks[vershina]
        return [self.vershinalar[j]
                for j, qiymat in enumerate(self.matritsa[i]) if qiymat != 0]

    def chiz(self):
        print("     " + "  ".join(f"{v:>2}" for v in self.vershinalar))
        for i, qator in enumerate(self.matritsa):
            print(f"  {self.vershinalar[i]:>2} " + "  ".join(f"{q:>2}" for q in qator))


graf = MatritsaGraf(["A", "B", "C", "D"])
graf.qirra_qosh("A", "B")
graf.qirra_qosh("A", "C")
graf.qirra_qosh("B", "C")
graf.qirra_qosh("C", "D")

graf.chiz()
print("\nA va B bog'liqmi:", graf.bogliqmi("A", "B"))
print("C ning qo'shnilari:", graf.qoshnilar("C"))

from collections import defaultdict


class Graf:
    """Qo'shnilik ro'yxati asosidagi graf."""

    def __init__(self, yonaltirilgan=False):
        self._qoshnilar = defaultdict(list)
        self.yonaltirilgan = yonaltirilgan

    def vershina_qosh(self, vershina):
        _ = self._qoshnilar[vershina]        # bo'sh ro'yxat yaratadi

    def qirra_qosh(self, birinchi, ikkinchi, vazn=1):
        """O(1)."""
        self._qoshnilar[birinchi].append((ikkinchi, vazn))
        if not self.yonaltirilgan:
            self._qoshnilar[ikkinchi].append((birinchi, vazn))

    def qoshnilar(self, vershina):
        """O(1) - ro'yxatning kuchli tomoni."""
        return self._qoshnilar[vershina]

    def bogliqmi(self, birinchi, ikkinchi):
        """O(daraja) - qo'shnilarni ko'rib chiqish kerak."""
        return any(q == ikkinchi for q, _ in self._qoshnilar[birinchi])

    def vershinalar(self):
        return list(self._qoshnilar.keys())

    def qirralar_soni(self):
        jami = sum(len(q) for q in self._qoshnilar.values())
        return jami if self.yonaltirilgan else jami // 2

    def chiz(self):
        for vershina in sorted(self._qoshnilar):
            bogliqlar = ", ".join(
                f"{q}({v})" if v != 1 else str(q)
                for q, v in self._qoshnilar[vershina]
            )
            print(f"  {vershina} -> {bogliqlar}")


graf = Graf()
for a, b in [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]:
    graf.qirra_qosh(a, b)

graf.chiz()
print(f"\nVershinalar: {len(graf.vershinalar())}, qirralar: {graf.qirralar_soni()}")

# Toshkent metrosining soddalashtirilgan sxemasi
metro = {
    "Chilonzor":     ["Mirzo Ulug'bek", "Novza"],
    "Novza":         ["Chilonzor", "Milliy bog'"],
    "Milliy bog'":   ["Novza", "Xalqlar do'stligi"],
    "Xalqlar do'stligi": ["Milliy bog'", "Paxtakor"],
    "Paxtakor":      ["Xalqlar do'stligi", "Mustaqillik maydoni", "Alisher Navoiy"],
    "Mustaqillik maydoni": ["Paxtakor", "Amir Temur xiyoboni"],
    "Alisher Navoiy": ["Paxtakor", "G'afur G'ulom"],
    "G'afur G'ulom": ["Alisher Navoiy"],
    "Amir Temur xiyoboni": ["Mustaqillik maydoni"],
    "Mirzo Ulug'bek": ["Chilonzor"],
}

print(f"Bekatlar soni: {len(metro)}")
print(f"Paxtakordan yo'nalishlar: {metro['Paxtakor']}")

# Eng ko'p bog'lanishga ega bekat
eng_gavjum = max(metro, key=lambda b: len(metro[b]))
print(f"Eng gavjum tugun: {eng_gavjum} ({len(metro[eng_gavjum])} ta yo'nalish)")

def darajalar(graf):
    """Har bir vershinaning darajasini hisoblaydi."""
    return {v: len(qoshnilar) for v, qoshnilar in graf.items()}


for bekat, daraja in sorted(darajalar(metro).items(), key=lambda j: -j[1])[:4]:
    ustun = "#" * daraja
    print(f"{bekat:<22}{daraja}  {ustun}")

def toliq_grafmi(graf):
    """Har bir vershina qolgan hammasi bilan bog'langanmi?"""
    n = len(graf)
    return all(len(qoshnilar) == n - 1 for qoshnilar in graf.values())


kichik_jamoa = {
    "Husanboy": ["Sardor", "Malika"],
    "Sardor": ["Husanboy", "Malika"],
    "Malika": ["Husanboy", "Sardor"],
}
print("To'liq grafmi:", toliq_grafmi(kichik_jamoa))
print("Metro to'liq grafmi:", toliq_grafmi(metro))