結果

問題 No.3087 University Coloring
ユーザー PNJ
提出日時 2025-04-04 23:05:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 995 ms / 2,000 ms
コード長 865 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 108,296 KB
最終ジャッジ日時 2025-04-04 23:06:10
合計ジャッジ時間 26,842 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind():
  def __init__(self, n): self.data = [-1 for _ in range(n)]
  
  def find(self, x):
    stack = []
    while self.data[x] >= 0:
      stack.append(x)
      x = self.data[x]
    while len(stack):
      y = stack.pop()
      self.data[y] = x
    return x
  
  def unite(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y: return
    if self.data[x] > self.data[y]: x, y = y, x
    self.data[x] += self.data[y]
    self.data[y] = x
    return
  
  def same(self, x, y): return self.find(x) == self.find(y)
  
  def size(self, x): return -self.data[self.find(x)]

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b, c = map(int, input().split())
  E.append((c, a - 1, b - 1))
E.sort()
ans = 0
uf = UnionFind(N)
while len(E):
  c, a, b = E.pop()
  if uf.same(a, b):
    continue
  uf.unite(a, b)
  ans += c
print(ans * 2)
0