結果

問題 No.2664 Prime Sum
コンテスト
ユーザー なえしら
提出日時 2024-07-24 00:32:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 3,203 bytes
コンパイル時間 674 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 73,552 KB
最終ジャッジ日時 2024-07-24 00:32:32
合計ジャッジ時間 3,947 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DirectedGraph:
  def __init__(self, order):
    self._order = order
    self._size = 0
    self._vertex = [[[], []] for _ in range(order)]
    self._edge = []
  def order(self): return self._order
  def size(self): return self._size
  def __get__(self, key):
    if key == 0: return self._vertex
    elif key == 1: return self._edge
  def add_vertex(self, *args):
    self._order += 1
    self._vertex.append([[], [], *args])
  def add_arc(self, v1, v2, *args):
    e = self._size
    self._size += 1
    self._vertex[v1][0].append(e)
    self._vertex[v2][1].append(e)
    self._edge.append([v1, v2, *args])
  def endpoint(self, e, v=None):
    v1, v2 = self._edge[e][:2]
    if v is None: return v1, v2
    return v ^ v1 ^ v2
  def indegree(self, v):
    return len(self._vertex[v][0])
  def outdegree(self, v):
    return len(self._vertex[v][1])

class UndirectedGraph(DirectedGraph):
  def add_edge(self, v1, v2, *args):
    e = self._size
    self._size += 1
    self._vertex[v1][0].append(e)
    self._vertex[v2][0].append(e)
    self._edge.append([v1, v2, *args])
  def degree(self, v):
    return len(self._vertex[v][0])

class ConnectedComponents(UndirectedGraph):
  def __init__(self, order):
    super().__init__(order)
    self._components = []
    self._component = []
  def build(self):
    for i in range(self._order):
      self._vertex[i][1] = [-1]*2
    self._components.clear()
    self._component.clear()
    for i in range(self._order):
      if self._vertex[i][1][0] != -1: continue
      comp_idx = len(self._components)
      self._vertex[i][1] = [comp_idx, 0]
      que, flg = [i], True
      for v in que:
        v_clr = self._vertex[v][1][1]
        for e in self._vertex[v][0]:
          v2 = self.endpoint(e, v)
          if self._vertex[v2][1][0] == -1:
            self._vertex[v2][1][0] = comp_idx
            if flg: self._vertex[v2][1][1] = v_clr ^ 1
            que.append(v2)
          elif flg and self._vertex[v2][1][1] == v_clr:
            flg = False
      self._components.append([[], [], []])
      self._component.append([len(que), 0])
      for v in que:
        if not flg: self._vertex[v][1][1] = -1
        v_clr = self._vertex[v][1][1]
        self._components[comp_idx][v_clr].append(v)
        self._component[comp_idx][1] += self.degree(v)
      self._component[comp_idx][1] //= 2
  def __call__(self, k=None):
    if k is None: return self._components
    return sum(self._components[k], [])
  def __len__(self):
    return len(self._components)
  def order(self, k=None):
    if k is None: return self._order
    return self._component[k][0]
  def size(self, k=None):
    if k is None: return self._size
    return self._component[k][1]
  def __get__(self, key):
    if key == 2: return self._component
    return super().__get__(key)
  def is_connected(self):
    return len(self._components) <= 1
  def is_bipartite(self, k=None):
    if k is None:
      return all(not comp[-1] for comp in self._components)
    return not self._components[k][-1]


n, m = map(int, input().split())
X = ConnectedComponents(n)

for _ in range(m):
  a, b = map(int, input().split())
  X.add_edge(a-1, b-1)

X.build()
print("Yes" if X.is_bipartite() else "No")
0