結果

問題 No.1813 Magical Stones
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-11-22 12:43:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,171 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 128,136 KB
最終ジャッジ日時 2024-11-22 12:43:27
合計ジャッジ時間 17,834 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 31
権限があれば一括ダウンロードができます

ソースコード

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

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=x
l=[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:
return
if rx>ry:
rx,ry=ry,rx
r[ry]=rx
return
r=list(range(n))
for a,b in e:
union(a,b)
c1=sum(root(i)==i for i in range(n))
c1-=c1==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
d=[0]*l
E=[[] for i in range(l)]
for a,b in e:
if c[a]!=c[b]:
E[c[a]]+=[c[b]]
d[c[b]]+=1
v=[0]*l
f=[0]*l
q=[i for i in range(l)]
for s in q:
if len(E[s])>0:
for t in E[s]:
if v[t]==0:
v[t]=1
f[t]+=1
else:
f[s]+=1
c2=sum(f[i]==2 for i in range(l))
print(c1+c2)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0