目指せ水色コーダー！！！！！！

ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！

###過去記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】

#「Part6」〜深さ優先探索(DFS)編〜
以下の4問を解いていきます！

#####深さ優先探索
24　ALDS_11_B - 深さ優先探索　基本問題です。
25　AOJ 1160 - 島はいくつある？　グラフの連結成分数は、深さ優先探索で計算できます。
26　AtCoder Beginner Contest 138 D - Ki　木構造の問題の多くは、深さ優先探索を使います。
27　JOI 2009 予選 4 - 薄氷渡り　深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。

#DFSの前提知識
・以下の3点を前提として、記事を書いていきます！
①スタックとキューについて
まずはけんちょんさんの記事
スタックとキューを極める！〜考え方と使い所を特集〜
を読んで、スタックとキューについて雰囲気理解する！

②DFSとグラフについて
またまたけんちょんさんの記事
DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【前編】
DFS (深さ優先探索) 超入門！〜グラフ・アルゴリズムの世界への入口〜【後編】
を読んで、DFSとグラフについて雰囲気理解する！

③あとは、PythonでのDFSの具体的な実装方法
として、
以下のサイトがわかりやすかったので、この2つのサイト
◆ふつうのグラフまたは木の場合
Pythonでアルゴリズム（深さ優先探索、dfs）
◆グリッドグラフの場合
Pythonで深さ優先探索(DFS)を実装してみる-ATC001
をじっくり読んでDFSとグラフについて深く理解する！

①②③の前提があれば、あとは実際に手を動かせば身につきます！！！

※補足1
DFSは再帰VerとスタックVerの2つの実装方法がありますが、
この記事ではスタックVerの実装に統一します！！！
(BFSに応用が効きやすい？+速度も早い？+スタックオーバーフローを起こさない？ため)

※補足2
今回(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！
【Python】競プロテンプレ【AtCoder】
テンプレ用の記事も作ったので、よかったら使ってください〜

#24　ALDS_11_B - 深さ優先探索
典型的なグラフ問題！

graph = {i:collections.deque() for i in range(1,N+1)}
または、
graph = {i:[] for i in range(1,N+1)}
これがグラフのテンプレ！

DFSの実装初めてだったけど、
上のサイトの通り実装してみるとなんとか実装できた！
コードは長いけど、難易度はたいしたことない！！！

ポイントは、この2行！！！

seen[j] = 1
stack.append(j)

seen[g_NO] = 1
stack.append(g_NO)

〜覚え方〜
①家政婦は見た！（ドラマ）ので、
seenを0(False)→1(True)にする！
②家政婦は見たら、ストックに入れます！！！
（家政婦がゴミを見たので、ゴミ箱に入れるイメージ！！！）

このイメージが頭にあれば、実装の時に脳死でコードが書ける！

test.py

import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
    global time
    seen[j] = 1
    stack.append(j)
    time += 1
    seentime[j] = time
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            time += 1
            donetime[s] = time
            continue
        g_NO = graph[s].popleft()
        if seen[g_NO]:
            continue
        seen[g_NO] = 1
        stack.append(g_NO)
        time += 1
        seentime[g_NO] = time
for j in range(1,n+1):
    if seen[j]:
        continue
    dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
    print(k,a,b)

def dfs()なんて書く必要ないけど、DFSの記述とわかりやすいようにdefにしてみた！

また、グラフ問題は
「0」からではなく「1」から始まることがほとんどだと思うので
1_indexedでコード全体を統一！

globalも初めて使ってみたけどなるほど！って感じ！

あとコードを書いていて意識したことは、
continueをできるだけ使って、条件以下のコードを走らせないようにして可読性をあげました！
DFSは特にネストが深くなりがち！（＝複雑になりがち＝バグがうまれやすくなる！）
※過去記事参照
【リーダブルコード】内容を5つ抜粋！【競技プログラミング】

家政婦は見た！（2回目）

#25　AOJ 1160 - 島はいくつある？
典型的なグリッドグラフ問題！
ふつうのグラフの問題と考え方は同じ！
上のサイトを参考にしたが、案外スラスラかけた！
家政婦は見た！（3回目）

test.py

import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
    w,h = LI()
    if w==h==0:
        break
    ans = 0
    c = [LI() for _ in range(h)]
    seen = [[0]*w for _ in range(h)]
    stack = []
    dhdw = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
    def dfs(H,W):
        seen[H][W] = 1
        stack.append([H,W])
        while stack:
            sh,sw = stack.pop()
            for dh,dw in dhdw:
                nh,nw = sh+dh,sw+dw
                if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or c[nh][nw]==0:
                    continue
                seen[nh][nw] = 1
                stack.append([nh,nw])
    for H,W in itertools.product(range(h),range(w)):
        if seen[H][W] or c[H][W]==0:
            continue
        ans += 1
        dfs(H,W)
    print(ans)

#26　AtCoder Beginner Contest 138 D - Ki
Difficulty:923
初見で解けませんでした！！！
計算量でつまずき、根の考え方でもつまずいた！
だけど、次からは似た問題きても解ける**「木」**がする！！！

ポイントはこの2点！

木は無向グラフとして考える
問題文よりこの木全体の根は頂点1

根より下にある頂点は全て、基準の根のポイントが追加されていく感じ〜
ACにならなかった人はこちらの記事も参考に！！！
AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について (修正版)

家政婦は見た！（4回目）

test.py

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_indexed
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_indexed
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

ちなみに、
冒頭の補足2で記載した

今回(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！

これの原因はこの問題ですw

TLEで苦戦していてところ、できる人のコード見てたら、
sys.stdin.readline()
使ってるなぁ・・・
一応使ってみるかと使ったところ、まさかのACになってびっくり！
調べてみると、input()が激遅であることが判明！！！
参考記事
Pythonの知っておくと良い細かい処理速度の違い8個

ほかにも計算量について、コードの改善余地はあるが、
(abやpxの受け取りのところとか)
ACになったからまあいいや〜

#27　JOI 2009 予選 4 - 薄氷渡り
こちらも初見で解けませんでした！！！

まさかの**家政婦は見た！(seen)**が使えない問題！！！
過去記事
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
の部分和問題もDFSで解ける問題なのですが、
**家政婦は見た！(seen)**が使えない場合は、**家政婦は見た！(seen)**に変わるものを自分で考えないといけないので難易度高め！

Part3の部分和問題：indexとsum
今回の問題：スタック時の位置、過去の履歴

難しい問題をたくさん解いて慣れていくしかなさそう！

test.py

import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
m = I()
n = I()
area = [LI() for _ in range(n)]
ans = 0
dndm = [[1,0],[-1,0],[0,1],[0,-1]]
stack = [] #スタック時の位置、過去の履歴
def dfs(i,j):
    global ans
    stack.append([[i,j],set()])
    while stack:
        [sn,sm],history = stack.pop()
        ans = max(ans,len(history))
        for dn,dm in dndm:
            nn,nm = sn+dn,sm+dm
            if not(0<=nn<=n-1) or not(0<=nm<=m-1) or area[nn][nm]==0 or ((nn,nm) in history):
                continue
            stack.append([[nn,nm],history | {(nn,nm)}])
for i,j in itertools.product(range(n),range(m)):
    if area[i][j]==1:
        dfs(i,j)
print(ans)

※補足

history | {(nn,nm)}

の
|は和集合です！(ビット演算子のORでもある)
また、
&が積集合です！(ビット演算子のANDでもある)
^がどちらか一方の集合です！(ビット演算子のXORでもある)
※過去記事参照
【Python】ARC006A(集合(set)最強説)【AtCoder】

次回は、以下の6問を解いていきます！

#####幅優先探索
28　ALDS_11_C - 幅優先探索　基本問題です。
29　AtCoder Beginner Contest 007 C - 幅優先探索　重み無しグラフの最短経路問題は、幅優先探索で解けます。
30　JOI 2011 予選 5 - チーズ
31　JOI 2012 予選 5 - イルミネーション　少し実装が重いですが、頑張れば解けます。
32　AOJ 1166 - 迷図と命ず　実装が少し重いです。
33　AtCoder Beginner Contest 088 D - Grid Repainting　これが解ければ、幅優先探索に慣れたと思って良いです。

Part6/22
おわり！

次(Part7/22)へ