67 lines
No EOL
1.8 KiB
Python
67 lines
No EOL
1.8 KiB
Python
import sys
|
|
|
|
|
|
data = sys.stdin.read().split()
|
|
ptr = 0
|
|
|
|
|
|
while ptr < len(data):
|
|
n = int(data[ptr])
|
|
ptr += 1
|
|
m = int(data[ptr])
|
|
ptr += 1
|
|
N = 2 * n
|
|
g = [[] for _ in range(N)]
|
|
gr = [[] for _ in range(N)]
|
|
for _ in range(m):
|
|
i1 = int(data[ptr]); ptr += 1
|
|
e1 = int(data[ptr]); ptr += 1
|
|
i2 = int(data[ptr]); ptr += 1
|
|
e2 = int(data[ptr]); ptr += 1
|
|
u_neg = 2 * i1 + (1 - e1)
|
|
v_neg = 2 * i2 + (1 - e2)
|
|
u_pos = 2 * i1 + e1
|
|
v_pos = 2 * i2 + e2
|
|
g[u_neg].append(v_pos)
|
|
gr[v_pos].append(u_neg)
|
|
g[v_neg].append(u_pos)
|
|
gr[u_pos].append(v_neg)
|
|
visited = [False] * N
|
|
order = []
|
|
for i in range(N):
|
|
if not visited[i]:
|
|
stack = [(i, 0)]
|
|
visited[i] = True
|
|
while stack:
|
|
cur, edge_idx = stack[-1]
|
|
if edge_idx < len(g[cur]):
|
|
next_node = g[cur][edge_idx]
|
|
stack[-1] = (cur, edge_idx + 1)
|
|
if not visited[next_node]:
|
|
visited[next_node] = True
|
|
stack.append((next_node, 0))
|
|
else:
|
|
order.append(cur)
|
|
stack.pop()
|
|
comp = [-1] * N
|
|
c_id = 0
|
|
for i in range(N - 1, -1, -1):
|
|
start_node = order[i]
|
|
if comp[start_node] == -1:
|
|
c_id += 1
|
|
stack = [start_node]
|
|
comp[start_node] = c_id
|
|
while stack:
|
|
cur = stack.pop()
|
|
for neighbor in gr[cur]:
|
|
if comp[neighbor] == -1:
|
|
comp[neighbor] = c_id
|
|
stack.append(neighbor)
|
|
|
|
res = []
|
|
for i in range(n):
|
|
if comp[2 * i + 1] > comp[2 * i]:
|
|
res.append("1")
|
|
else:
|
|
res.append("0")
|
|
print("".join(res)) |