zad2.py

from checker import maxclique_checker
from lexBFS import lexBFS, Node, gen_nodes_list

def maxclique(V, L): # zwraca rozmiar największej kliki
    G = gen_nodes_list(V, L)
    G : list[Node]
    order = lexBFS(G, V)
    og_idx_to_order = [None] * (V + 1)
    for i in range(V):
        og_idx_to_order[order[i]] = i

    RN_plus_v = [set() for _ in range(V + 1)]
    max_len = 0

    for i in range(1, V): # nie ma sensu sprawdzać pierwszego elementu order, bo wszystko puste
        v = order[i]
        for u in G[v].out:
            u_idx = og_idx_to_order[u]
            if u_idx < i:
                RN_plus_v[v].add(u)
        
        RN_plus_v[v].add(v)
        k = len(RN_plus_v[v])
        if k > max_len:
            max_len = k

    return max_len


maxclique_checker(maxclique)