"""2-approximation vertex cover: greedily pick both endpoints of an uncovered edge."""


def approx_vertex_cover(adj):
    n = len(adj)
    cover = [False] * n
    removed = [False] * n
    done = False
    while not done:
        done = True
        for u in range(n):
            if removed[u]:
                continue
            for v in range(u + 1, n):
                if not removed[v] and adj[u][v] == 1:
                    cover[u] = True
                    cover[v] = True
                    removed[u] = True
                    removed[v] = True
                    done = False
                    break
    return cover


if __name__ == "__main__":
    adj = [
        [0, 1, 0, 1],
        [1, 0, 1, 0],
        [0, 1, 0, 1],
        [1, 0, 1, 0],
    ]
    result = approx_vertex_cover(adj)
    print(f"cover = {result}")
    print(f"vertices: {[i for i, c in enumerate(result) if c]}")