【今日の精進】ARC111D - Orientation

毎日格上の問題を倒すやつの20日目です。¹

問題リンク

atcoder.jp

問題概要

無向グラフが与えられるよ。

頂点 から行ける頂点数が になるように辺に向きをつけてね。

解法

から に辺を張るとき、明らかに から行ける頂点は から行ける頂点数以上です。

そのため、 が異なる頂点同士の向きは速攻で決められます。

それ以外は明らかに強連結でないといけません。

強連結にするためには、DFSをするとなんかうまくいきます。

解の存在が保証されているので、これでよいです。

提出コード

def dfs(p):
    global went,use
    went[p]=True
    for i in gr[p]:
        if c[p]!=c[i]:
            continue
        if (i,p) not in deledge and (p,i) not in deledge:
            deledge.add((i,p))
            use.append((i,p))
        if not(went[i]):
            dfs(i)

N,M=map(int,input().split())
edge={}
gr=[set() for i in range(N)]
use=[]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[(a,b)]=("->",i)
    edge[(b,a)]=("<-",i)
    gr[a].add(b)
    gr[b].add(a)
c=list(map(int,input().split()))
for i in range(N):
    for j in range(i+1,N):
        if j in gr[i]:
            if c[i]<c[j]:
                use.append((j,i))
            elif c[i]>c[j]:
                use.append((i,j))
went=[False for i in range(N)]
deledge=set()
for i in range(N):
    if not(went[i]):
        dfs(i)
ans=[None for i in range(M)]
for i in use:
    ans[edge[i][1]]=edge[i][0]
print("\n".join(ans))

Submission #46420516 - AtCoder Regular Contest 111

感想

わかっちゃえば自明だね

---

1. ここまで続いたのは奇跡↩