Статья Автор: Мастикова София

нн

from collections import deque

def topsort(g):
    n = len(g)
    indeg = [0] * n
    
    for v in range(n):
        for to in g[v]:
            indeg[to] += 1
    
    q = deque()
    for v in range(n):
        if indeg[v] == 0:
            q.append(v)
    
    res = []
    while q:
        v = q.popleft()
        res.append(v)
        
        for to in g[v]:
            indeg[to] -= 1
            if indeg[to] == 0:
                q.append(to)
    
    if len(res) != n:
        return None
    
    return res


from collections import deque

def is_bipartite(g):
    n = len(g)
    color = [-1] * n
    
    for start in range(n):
        if color[start] != -1:
            continue
            
        color[start] = 0
        q = deque([start])
        
        while q:
            v = q.popleft()
            
            for to in g[v]:
                if color[to] == -1:
                    color[to] = color[v] ^ 1
                    q.append(to)
                elif color[to] == color[v]:
                    return False
    
    return True

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать