ABC287 C - Path Graph?
https://atcoder.jp/contests/abc287/tasks/abc287_c
提出
code: python
from collections import deque
n, m = map(int, input().split())
uv = list(map(int, input().split())) for _ in range(m)
g = [[] for _ in range(n+1)]
visited = False * (n+1)
for u, v in uv:
gu.append(v)
gv.append(u)
# print(g)
# ], 3, 4, 3, 1, 2, [2
q = deque()
q.append(1)
visited1 = True
while q:
now = q.popleft()
for next in gnow:
if visitednext:
continue
else:
if abs(now-next) > 2:
print("No")
exit()
visitednext = True
q.append(next)
if sum(visited) == n:
print("Yes")
else:
print("No")
解答
code: python
from collections import defaultdict
from collections import deque
n, m = map(int, input().split())
uv = list(map(int, input().split())) for _ in range(m)
d = defaultdict(list)
for u, v in uv:
du.append(v)
dv.append(u)
visited = False * (n+1)
# print(d)
# {1: 3, 3: 1, 2, 4: 2, 2: 4, 3}
que = deque()
que.append(1)
visited1 = True
while que:
now = que.popleft()
for next in dnow:
if visitednext:
continue
else:
visitednext = True
que.append(next)
if sum(visited) != n:
print("No")
exit()
# 頂点の次数が 2 以下、1 が 2 個
# 頂点 1 と 4 が結ばれてはいけない、というわけではなく、ループがないか、というのが条件
c = 0
for v in d.values():
if len(v) == 1:
c += 1
if len(v) > 2:
print("No")
exit()
if c == 2:
print("Yes")
else:
print("No")
テーマ
#graph
メモ
https://note.com/kai1023/n/nc289fa9849b9#ba8fe89a-97d6-4099-99f0-456f47ac33ae
提出
code: python
from collections import defaultdict
from collections import deque
n, m = map(int, input().split())
uv = list(map(int, input().split())) for _ in range(m)
d = defaultdict(list)
for u, v in uv:
du.append(v)
dv.append(u)
# print(d)
# {1: 3, 3: 1, 2, 4: 2, 2: 4, 3}
visited = False * (n+1)
if m == 0:
print("No")
exit()
que = deque()
que.append(1)
while que:
next = que.popleft()
if visitednext:
continue
else:
visitednext = True
for n in dnext:
que.append(n)
# 訪れてない頂点があったら OUT
# 2 以上繋いでたら OUT