ABC335 E - Non-Decreasing Colorful Path

atcoder.jp

問題

• 連結なN頂点の無向グラフが与えられるよ
• 頂点には数字が書かれてるよ
• 1からNまでの単純パス(同じ頂点を複数回通らない)のうち、一番スコアの高いパスのスコアを教えてね
  • パスの頂点に書かれた数字が広義単調増加になってる場合、数字の種類数が得点になるよ

成約

• $ 2 \leq N \leq 2\times10^5$
• $ N-1 \leq M \leq 2\times10^5$
• $ 1 \leq A_i \leq 2\times10^5$

思考

• 本番でAC出来なかったのでとても悔しい
• グラフが連結なので、最低でもスコア0は成立するからそれ以上の話にする
• 辺を受け取る時に、両端の頂点の数字を見て…
  • 両端の数字が違うなら、小さい数字の頂点→大きい数字の頂点に辺を繋ぐ
  • 両端の数字が一緒なら、双方向に辺を繋ぐ
• 強連結成分分解してDAGにしてから、トポロジカルソートして、0からNまでの種類最大値をBFS的に見ていく話
• ACLのSCC使うと、トポロジカルソート順に吐いてくれるよ！
  • 多分無限回使うのでちゃんとACL使いこなせるようになろうね

コード

from atcoder.scc import SCCGraph

N,M = map(int,input().split())
A_L = list(map(int, input().split()))

SCC = SCCGraph(N)
edge_L = [[] for i in range(N)]
for i in range(M):
    U,V = map(int,input().split())
    U-=1
    V-=1
    if A_L[U] == A_L[V]:
        SCC.add_edge(U,V)
        SCC.add_edge(V,U)
        edge_L[U].append(V)
        edge_L[V].append(U)
    elif A_L[U] < A_L[V]:
        SCC.add_edge(U,V)
        edge_L[U].append(V)
    else:
        SCC.add_edge(V,U)
        edge_L[V].append(U)

score = [0]*N
score[0] = 1

for group in SCC.scc():
    tmp = 0
    next_s = set()
    group_s = set(group)
    for node in group:
        tmp = max(tmp,score[node])
    if tmp == 0:continue

    for node in group:
        score[node] = tmp
        for next_node in edge_L[node]:
            next_s.add(next_node)

    for next_node in next_s:
        if next_node in group_s:continue
        score[next_node] = max(score[next_node],tmp+1)
print(score[-1])