Biểu diễn đồ thị

def tao_ma_tran_ke(n, canh, co_huong=False):
    """
    n: số đỉnh (đánh số 0 đến n-1)
    canh: [(u, v)] hoặc [(u, v, trong_so)]
    """
    matrix = [[0] * n for _ in range(n)]
    for edge in canh:
        if len(edge) == 3:
            u, v, w = edge
        else:
            u, v, w = edge[0], edge[1], 1
        matrix[u][v] = w
        if not co_huong:
            matrix[v][u] = w
    return matrix

# Đồ thị vô hướng 4 đỉnh
canh = [(0,1), (0,2), (1,3), (2,3)]
matrix = tao_ma_tran_ke(4, canh)
for row in matrix:
    print(row)
# [0, 1, 1, 0]
# [1, 0, 0, 1]
# [1, 0, 0, 1]
# [0, 1, 1, 0]

# Kiểm tra cạnh O(1)
print("Có cạnh (0,1):", matrix[0][1] != 0)   # True
print("Có cạnh (0,3):", matrix[0][3] != 0)   # False

from collections import defaultdict

def tao_ds_ke(n, canh, co_huong=False, co_trong_so=False):
    """Xây dựng danh sách kề từ danh sách cạnh."""
    graph = defaultdict(list)
    for edge in canh:
        if co_trong_so:
            u, v, w = edge
            graph[u].append((v, w))
            if not co_huong:
                graph[v].append((u, w))
        else:
            u, v = edge
            graph[u].append(v)
            if not co_huong:
                graph[v].append(u)
    return graph

# Đồ thị vô hướng đơn giản
canh = [(0,1), (0,2), (1,3), (2,3)]
g = tao_ds_ke(4, canh)
print(dict(g))
# {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}

# Đồ thị có hướng có trọng số
canh_w = [(0,1,4), (0,2,1), (2,1,2), (1,3,1), (2,3,5)]
gw = tao_ds_ke(4, canh_w, co_huong=True, co_trong_so=True)
print(dict(gw))
# {0: [(1,4),(2,1)], 2: [(1,2),(3,5)], 1: [(3,1)]}

# Duyệt hàng xóm
for v, w in gw[0]:
    print(f"  0 → {v} (trọng số {w})")

# Đồ thị có trọng số: list of (u, v, weight)
canh = [
    (0, 1, 4),
    (0, 2, 1),
    (2, 1, 2),
    (1, 3, 1),
    (2, 3, 5)
]

# Sắp xếp theo trọng số — dùng cho Kruskal's
canh_sap_xep = sorted(canh, key=lambda e: e[2])
for u, v, w in canh_sap_xep:
    print(f"  ({u},{v}) trọng số {w}")
# (0,2) 1
# (1,3) 1
# (2,1) 2
# (0,1) 4
# (2,3) 5

import sys
from collections import defaultdict

def doc_do_thi_vo_huong():
    """
    Đọc đồ thị từ stdin theo định dạng:
    Dòng 1: n m
    Dòng 2..m+1: u v [w]
    """
    input_data = """5 6
1 2
1 3
2 4
3 4
3 5
4 5""".strip().split('\n')

    it = iter(input_data)
    n, m = map(int, next(it).split())
    graph = defaultdict(list)
    for _ in range(m):
        parts = list(map(int, next(it).split()))
        u, v = parts[0] - 1, parts[1] - 1   # Chuyển về 0-indexed
        w = parts[2] if len(parts) == 3 else 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    return n, graph

n, g = doc_do_thi_vo_huong()
print(f"{n} đỉnh")
for u in sorted(g.keys()):
    print(f"  {u}: {g[u]}")

from collections import defaultdict

def thong_ke_do_thi(n, canh):
    """In số cạnh, bậc của từng đỉnh, đỉnh bậc cao nhất."""
    graph = defaultdict(list)
    for u, v in canh:
        graph[u].append(v)
        graph[v].append(u)

    print(f"Số đỉnh: {n}, Số cạnh: {len(canh)}")
    bac = {i: len(graph[i]) for i in range(n)}
    for i in range(n):
        print(f"  Đỉnh {i}: bậc {bac[i]}")
    dinh_cao_nhat = max(bac, key=bac.get)
    print(f"Đỉnh bậc cao nhất: {dinh_cao_nhat} (bậc {bac[dinh_cao_nhat]})")

canh = [(0,1),(0,2),(0,3),(1,2),(2,3)]
thong_ke_do_thi(4, canh)

def ma_tran_sang_ds_ke(matrix):
    """Chuyển ma trận kề → danh sách kề (có trọng số)."""
    n = len(matrix)
    graph = {i: [] for i in range(n)}
    for u in range(n):
        for v in range(n):
            if matrix[u][v] != 0:
                graph[u].append((v, matrix[u][v]))
    return graph

def ds_ke_sang_ma_tran(n, graph):
    """Chuyển danh sách kề (có trọng số) → ma trận kề."""
    matrix = [[0] * n for _ in range(n)]
    for u in graph:
        for v, w in graph[u]:
            matrix[u][v] = w
    return matrix

# Test
matrix = [
    [0, 3, 0, 7],
    [3, 0, 2, 0],
    [0, 2, 0, 1],
    [7, 0, 1, 0]
]
graph = ma_tran_sang_ds_ke(matrix)
print("Danh sách kề:", dict(graph))
matrix2 = ds_ke_sang_ma_tran(4, graph)
print("Ma trận gốc:", matrix == matrix2)   # True

from collections import defaultdict

def phan_tich_co_huong(n, canh):
    """
    Tính bậc vào (in-degree) và bậc ra (out-degree) cho đồ thị có hướng.
    Tìm đỉnh nguồn (bậc vào = 0) và đỉnh đích (bậc ra = 0).
    """
    in_deg  = [0] * n
    out_deg = [0] * n
    for u, v in canh:
        out_deg[u] += 1
        in_deg[v] += 1

    nguon = [i for i in range(n) if in_deg[i] == 0]
    dich  = [i for i in range(n) if out_deg[i] == 0]
    print(f"Bậc vào:  {in_deg}")
    print(f"Bậc ra:   {out_deg}")
    print(f"Đỉnh nguồn (in=0): {nguon}")
    print(f"Đỉnh đích  (out=0): {dich}")

# Pipeline: 0→1, 0→2, 1→3, 2→3, 3→4
canh = [(0,1),(0,2),(1,3),(2,3),(3,4)]
phan_tich_co_huong(5, canh)