結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-11-22 12:28:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,974 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 128,260 KB |
最終ジャッジ日時 | 2024-11-22 12:29:12 |
合計ジャッジ時間 | 16,520 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | AC * 1 WA * 39 |
ソースコード
n,m=map(int,input().split())e=[]for i in range(m):a,b=map(int,input().split())e+=[(a-1,b-1)]def root(x):p=xl=[p]while r[p]!=p:p=r[p]l+=[p]for p in l:r[p]=l[-1]return r[x]def union(x,y):rx=root(x)ry=root(y)if rx==ry:returnif rx>ry:rx,ry=ry,rxr[ry]=rxreturnr=list(range(n))for a,b in e:union(a,b)c1=sum(root(i)==i for i in range(n))c1-=c1==1class SCC():def __init__(self,n):self.n=nself.e=[[] for i in range(self.n)]self.re=[[] for i in range(self.n)]returndef add_edge(self,s,t):self.e[s]+=[t]self.re[t]+=[s]returndef scc(self):v=[0]*self.ng=[0]*self.no=[]for i in range(self.n):if v[i]==0:q=[i]while len(q)>0:s=q[-1]v[s]=1while g[s]<len(self.e[s]):t=self.e[s][g[s]]if v[t]==0:breakg[s]+=1if g[s]<len(self.e[s]):q+=[t]else:o+=[s]q.pop()c=[-1]*self.np=0for i in o[::-1]:if c[i]==-1:s=ic[s]=pq=[s]for s in q:for t in self.re[s]:if c[t]==-1:c[t]=pq+=[t]p+=1l=[[] for i in range(p)]for i in range(self.n):l[c[i]]+=[i]d=[0]*pfor s in range(self.n):for t in self.e[s]:if c[s]!=c[t]:d[c[t]]+=1ts=[]q=[i for i in range(p) if d[i]==0]for v in q:ts+=[v]for s in l[v]:for t in self.e[s]:if c[s]!=c[t]:d[c[t]]-=1if d[c[t]]==0:q+=[c[t]]return [l[ts[i]] for i in range(p)]g=SCC(n)for a,b in e:g.add_edge(a,b)l=g.scc()c=[0]*nfor i in range(len(l)):for j in l[i]:c[j]=id=[0]*len(l)for a,b in e:if c[a]!=c[b]:d[c[b]]+=1c2=sum(d[i]==0 for i in range(len(l)))print(c1+c2)