結果

問題 No.2910 単体ホモロジー入門
ユーザー るこーそーるこーそー
提出日時 2024-10-11 23:05:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,037 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 52,864 KB
最終ジャッジ日時 2024-10-11 23:05:24
合計ジャッジ時間 3,551 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
52,480 KB
testcase_01 AC 45 ms
52,480 KB
testcase_02 AC 42 ms
52,352 KB
testcase_03 AC 42 ms
52,224 KB
testcase_04 AC 42 ms
52,096 KB
testcase_05 AC 42 ms
52,480 KB
testcase_06 AC 42 ms
52,096 KB
testcase_07 AC 43 ms
52,352 KB
testcase_08 AC 42 ms
52,480 KB
testcase_09 AC 46 ms
52,480 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 43 ms
52,224 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 42 ms
52,352 KB
testcase_24 AC 41 ms
52,608 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 43 ms
52,480 KB
testcase_28 AC 42 ms
52,224 KB
testcase_29 WA -
testcase_30 AC 43 ms
52,224 KB
testcase_31 AC 42 ms
52,224 KB
testcase_32 WA -
testcase_33 AC 42 ms
52,224 KB
testcase_34 WA -
testcase_35 AC 41 ms
52,480 KB
testcase_36 AC 43 ms
52,352 KB
testcase_37 AC 41 ms
52,608 KB
testcase_38 AC 42 ms
52,480 KB
testcase_39 AC 42 ms
52,224 KB
testcase_40 AC 42 ms
52,224 KB
testcase_41 AC 43 ms
52,352 KB
testcase_42 AC 55 ms
52,352 KB
testcase_43 AC 42 ms
52,352 KB
testcase_44 AC 42 ms
52,480 KB
testcase_45 AC 42 ms
52,224 KB
testcase_46 AC 42 ms
52,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**5)
input=sys.stdin.readline
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

class SCCGraph:
  #ACLと同じ名前で実装したver.
  def __init__(self,n):
    self.n=n
    self.g=[[] for _ in range(self.n)]
    self.rg=[[] for _ in range(self.n)]
    
  def add_edge(self,u,v):
    self.g[u].append(v)
    self.rg[v].append(u)
  
  def _dfs(self,v,vis,order):
    vis[v]=True
    for nv in self.g[v]:
      if vis[nv]:continue
      self._dfs(nv,vis,order)
    order.append(v)
    return order
  
  def _dfs_stack(self,v,vis,order):
    stack=[(v,False)]
    while stack:
      v,done=stack.pop()
      if done:
        order.append(v)
      else:
        stack.append((v,True))
        vis[v]=True
        for nv in self.g[v]:
          if vis[nv]:continue
          stack.append((nv,False))
    return order
  
  def _rdfs(self,v,vis,group):
    vis[v]=True
    group.append(v)
    for nv in self.rg[v]:
      if vis[nv]:continue
      self._rdfs(nv,vis,group)
    return group

  def _rdfs_stack(self,v,vis,group):
    stack=[v]
    while stack:
      v=stack.pop()
      vis[v]=True
      group.append(v)
      for nv in self.rg[v]:
        if vis[nv]:continue
        stack.append(nv)
    return group
  
  def scc(self,dfs_stack=False,rdfs_stack=False):
    order=[]
    vis=[False]*self.n
    for v in range(self.n):
      if vis[v]:continue
      if dfs_stack:self._dfs_stack(v,vis,order)
      else:self._dfs(v,vis,order)
    order=order[::-1]
    
    groups=[]
    vis=[False]*self.n
    for v in order:
      if vis[v]:continue
      groups.append(self._rdfs_stack(v,vis,[]) if rdfs_stack else self._rdfs(v,vis,[]))
    
    return groups

n,m=map(int,input().split())
scc=SCCGraph(n)
for _ in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    scc.add_edge(u,v)  
    scc.add_edge(v,u)
V=list(map(lambda x:int(x)-1,input().split()))
V.sort()

groups=scc.scc()
for group in groups:
    group.sort()
    if group==V:
        print('No')
        exit()
print('Yes')
0