結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 17
権限があれば一括ダウンロードができます

ソースコード

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