ABC231D - Neighbors

考え方

「$A$と$B$が隣あっている」を「$A$と$B$に辺がはられている」と読み替えればグラフの問題になる．

横一列に並べられる条件は，

1. すべての頂点から出ている辺の本数が2以下であること
2. 閉路がないこと

である．閉路検出は次を参照：閉路検出 - 競プロはじめました

回答例

UnionFind

UnionFind木（UnionFind木 - 競プロはじめました）を使う方法．

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())

p = [-1] * N
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def merge(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[y] = x
  
deg = [0] * N
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  deg[A] += 1
  deg[B] += 1
  if root(A) == root(B) or deg[A] > 2 or deg[B] > 2:
    exit(print('No'))
  merge(A, B)
    
print('Yes')

【参考】Submission #27826173 - Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)

DFS

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  G[A].append(B)
  G[B].append(A)
  deg[A] += 1
  deg[B] += 1
  if deg[A] > 2 or deg[B] > 2:
    exit(print('No'))
    
seen = [False] * N
def f(par, cur):
  seen[cur] = True
  for chi in G[cur]:
    if par != chi:
      if seen[chi]:
        exit(print('No'))
      f(cur, chi)

for v in range(N):
  if not seen[v]:
    f(-1, v)
      
print('Yes')