結果

問題 No.1813 Magical Stones
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-11-22 14:43:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,705 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 126,108 KB
最終ジャッジ日時 2024-11-22 14:43:42
合計ジャッジ時間 13,549 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 34 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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=n
self.e=[[] for i in range(self.n)]
self.re=[[] for i in range(self.n)]
return
def add_edge(self,s,t):
self.e[s]+=[t]
self.re[t]+=[s]
return
def scc(self):
v=[0]*self.n
g=[0]*self.n
o=[]
for i in range(self.n):
if v[i]==0:
q=[i]
while len(q)>0:
s=q[-1]
v[s]=1
while g[s]<len(self.e[s]):
t=self.e[s][g[s]]
if v[t]==0:
break
g[s]+=1
if g[s]<len(self.e[s]):
q+=[t]
else:
o+=[s]
q.pop()
c=[-1]*self.n
p=0
for i in o[::-1]:
if c[i]==-1:
s=i
c[s]=p
q=[s]
for s in q:
for t in self.re[s]:
if c[t]==-1:
c[t]=p
q+=[t]
p+=1
l=[[] for i in range(p)]
for i in range(self.n):
l[c[i]]+=[i]
d=[0]*p
for s in range(self.n):
for t in self.e[s]:
if c[s]!=c[t]:
d[c[t]]+=1
ts=[]
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]]-=1
if 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]*n
for i in range(l):
for j in L[i]:
c[j]=i
do=[0]*l
di=[0]*l
for a,b in e:
if c[a]!=c[b]:
do[c[a]]=1
di[c[b]]=1
print(max(sum(do[i]==0 for i in range(l)),sum(di[i]==0 for i in range(l))))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0