結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-11-22 14:45:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 640 ms / 2,000 ms |
コード長 | 1,672 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 126,240 KB |
最終ジャッジ日時 | 2024-11-22 14:46:06 |
合計ジャッジ時間 | 13,544 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
n,m=map(int,input().split())e=[]for i in range(m):a,b=map(int,input().split())e+=[(a-1,b-1)]class 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()l=len(L)c=[0]*nfor i in range(l):for j in L[i]:c[j]=ido=[0]*ldi=[0]*lfor a,b in e:if c[a]!=c[b]:do[c[a]]=1di[c[b]]=1print(max(do.count(0),di.count(0))-(l==1))