結果
問題 | No.330 Eigenvalue Decomposition |
ユーザー |
![]() |
提出日時 | 2021-11-26 03:39:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 555 ms / 5,000 ms |
コード長 | 2,071 bytes |
コンパイル時間 | 258 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 16,768 KB |
最終ジャッジ日時 | 2024-06-28 20:08:20 |
合計ジャッジ時間 | 7,574 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter, deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _heappush_max(heap,item):heap.append(item)heapq._siftdown_max(heap, 0, len(heap)-1)def _heappushpop_max(heap, item):if heap and item < heap[0]:item, heap[0] = heap[0], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as Gcdread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlinesclass UnionFind:def __init__(self,n):self.n=nself.parents=[-1]*ndef Find(self,x):stack=[]while self.parents[x]>=0:stack.append(x)x=self.parents[x]for y in stack:self.parents[y]=xreturn xdef Union(self,x,y):x=self.Find(x)y=self.Find(y)if x==y:returnif self.parents[x]>self.parents[y]:x,y=y,xself.parents[x]+=self.parents[y]self.parents[y]=xdef Size(self,x):return -self.parents[self.Find(x)]def Same(self,x,y):return self.Find(x)==self.Find(y)def Members(self,x):root = self.Find(x)return [i for i in range(self.n) if self.Find(i)==root]def Roots(self):return [i for i, x in enumerate(self.parents) if x<0]def Group_Count(self):return len(self.Roots())def All_Group_Members(self):group_members = defaultdict(list)for member in range(self.n):group_members[self.Find(member)].append(member)return group_membersdef __str__(self):return '\n'.join(f'{r}: {m}' for r, m in self.All_Group_Members().items())N,M=map(int,readline().split())UF=UnionFind(N)for _ in range(M):A,B,C=map(int,readline().split())A-=1;B-=1UF.Union(A,B)ans=UF.Group_Count()print(ans)