提出 #60122479

---

ソースコード 拡げる

from collections import defaultdict, deque

def solve():
    N, M = map(int, input().split())
    testimonies = defaultdict(list)

    for _ in range(M):
        a, b, c = map(int, input().split())
        testimonies[a].append((b, c))
        testimonies[b].append((a, 1 - c))  # Reverse testimony for consistency

    # Status array: -1 means unvisited, 0 means not confused, 1 means confused
    status = [-1] * (N + 1)

    def bfs(start):
        queue = deque([(start, 0)])  # (villager, confusion state)
        status[start] = 0  # Assume not confused initially
        while queue:
            current, cur_status = queue.popleft()
            for neighbor, testimony in testimonies[current]:
                expected_status = cur_status ^ testimony
                if status[neighbor] == -1:
                    # Unvisited neighbor
                    status[neighbor] = expected_status
                    queue.append((neighbor, expected_status))
                elif status[neighbor] != expected_status:
                    # Contradiction found
                    return False
        return True

    for i in range(1, N + 1):
        if status[i] == -1:  # Not visited
            if not bfs(i):
                print(-1)
                return

    # Generate the result string
    result = ''.join(map(str, status[1:]))
    print(result)

solve()

提出情報

ジャッジ結果