結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-11-22 13:31:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,065 bytes |
コンパイル時間 | 396 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 133,256 KB |
最終ジャッジ日時 | 2024-11-22 13:32:02 |
合計ジャッジ時間 | 14,239 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 32 |
ソースコード
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]=id=[0]*lE=[[] for i in range(l)]for a,b in e:if c[a]!=c[b]:E[c[a]]+=[c[b]]d[c[b]]+=1v=[0]*lf=[0]*lq=[i for i in range(l) if d[i]==0]for s in q:if len(E[s])>0:f[s]+=1for t in E[s]:if v[t]==0:v[t]=1f[t]+=1q+=[t]E=[[] for i in range(l)]for a,b in e:if c[a]!=c[b]:E[c[a]]+=[c[b]]E[c[b]]+=[c[a]]v=[0]*lv[0]=1q=[0]for s in q:for t in E[s]:if v[t]==0:v[t]=1q+=[t]print(sum(f[i]!=2 for i in range(l))-(0 not in v))