Submission #49168754

---

Source Code Expand

#ABC335E Non-Decreasing Colorful Path  UnionFind解

#UnionFind　使用時には UnionFind(N)で関数宣言を。
class UnionFind:
    def __init__(self,N):
        self._parent=[-1 for i in[0]*N]  #子なら親の頂点番号、親なら頂点数を負値で入力

    def find(self,v):  #頂点vの親を探す。同時に経路圧縮する
        if self._parent[v]<0:return v
        vertices=[]
        while self._parent[v]>=0:vertices.append(v);v=self._parent[v]
        for i in vertices:self._parent[i]=v
        return v

    def unite(self,x,y):  #頂点xとyを併合し、併合の有無を返す
        x,y=self.find(x),self.find(y)
        if x==y:return 0
        if self._parent[x]>self._parent[y]:x,y=y,x  #負値で管理している点に注意
        self._parent[x]+=self._parent[y];self._parent[y]=x;return 1

    def same(self,x,y):return self.find(x)==self.find(y)   #xとyは同一集合か返す
    def size(self,x):  return -self._parent[self.find(x)]  #xの集合のサイズを求める


#入力受取
N,M = map(int,input().split())
A = list(map(int,input().split()))

#UnionFindを準備
UF = UnionFind(N)

#有向グラフとして辺を受け取り
G = [[] for _ in range(N)]
for _ in range(M):
    u,v = map(int, input().split())
    if A[u-1]  < A[v-1]: G[u-1].append(v-1)
    if A[u-1] == A[v-1]: UF.unite(u-1,v-1)
    if A[u-1] >  A[v-1]: G[v-1].append(u-1)

#DAG上のDPを解く  DP[i]: 頂点iの最長パス
#親の頂点でしかDPの更新を行わない点に注意
DP = [-10**18] * N
DP[UF.find(0)] = 1
Q = [[] for _ in range(max(A)+1)]  #Q[A[i]]: 該当する頂点i
for i in range(N): Q[A[i]].append(i)

#A[i]の昇順にDP
for L in Q:
    for i in L:
        now = UF.find(i)  #頂点iの親
        for j in G[i]:
            next = UF.find(j)  #頂点jの親
            DP[next] = max(DP[next], DP[now]+1)
        
#答えを出力
print(max(0, DP[UF.find(-1)]))

Submission Info

Judge Result