デッドロックを検出せよ
コンピュータにおける「データベース」とは、情報を管理するための入れ物で、「データベースマネジメントシステム(DBMS)」とは、その管理をする仕組みです。複数のユーザが利用するデータベースでは、DBMS は慎重に構築する必要があります。
例えば、倉庫から商品を１つ取り出した人が、データベースに対して以下の処理を行うとしましょう。
(1) 商品の個数 N をデータベースから読む。
(2) 新たな商品の個数 N-1 をデータベースに書き込む。
ユーザ１が(1)を終えて(2)を始める前に、別のユーザ２が倉庫から商品を取り出して(1)を行ったとします。ユーザ２もユーザ１と同じ個数を読むので、２人が(2)を終えたときには商品は２個減るのにデータベース上では１個しか減らないというおかしな結果になります。このような問題を防ぐために、DBMS は特定のデータを操作中のユーザに、そのデータを「ロック」する権利を与えます。ロックされていれば、他のユーザはその値を操作できなくなるので、おかしな結果を返すことはなくなります。
これで安全に操作できることは保証されますが、今度は別の問題が起こります。例えば、ユーザ１とユーザ２が以下のような順番でデータＡとＢをロックしようとしたらどうなるでしょうか？
(1) ユーザ１がデータＡのロックを試みる → 成功（データＡがロック中になる）
(2) ユーザ２がデータＢのロックを試みる → 成功（データＢがロック中になる）
(3) ユーザ１がデータＢのロックを試みる → データＢがロック中なのでユーザ１は待つ
(4) ユーザ２がデータＡのロックを試みる → データＡがロック中なのでユーザ２は待つ
(4)を実行した時点では、ユーザ１がＡ、ユーザ２がＢをロックしているので、(3)(4)は永久に成功しませ
ん。これを「デッドロック」と呼びます。DBMS はこれを検出しなければなりません。
ある時点でデッドロックが起きているかどうかは、その時点でのすべてのユーザとデータの依存関係を書き、循環ができているかどうかで判断できます。依存関係は，ユーザがデータをロック済みの場合はデータからユーザの向きに矢印を、ユーザがデータのロックを試行していて待ち状態になっている場合はユーザからデータの向きに矢印を書くことで表します。
上の(1)から(4)の例であれば、(4)を実行した時点での依存関係は右上のような図になります。このとき、矢印の方向に進むと、ユーザ１→データＢ→ユーザ２→データＡ→ユーザ１という循環ができているため、デッドロックが起きていることがわかります。DBMS の苦労を体験するため、あなたにここでやってもらいたいのは、このようなデッドロックを検出するプログラムを作成することです。
入力
入力は以下の形式で与えられる。
N rel1 rel2 : relN
１行目にユーザとデータの依存関係の数 N (1 ≤ N ≤ 1000) が与えられる。続く N 行に、ユーザとデータの依存関係 reli が与えられる。依存関係は lock と wait の２種類あり、各 reli は以下のいずれかの形式で与えられる。
u lock d
または
u wait d
u lock d は、ユーザ u (1 ≤ u ≤ 100) が、データ d (1 ≤ d ≤ 100) をロック済みであることを表す。
u wait d は、ユーザ u (1 ≤ u ≤ 100) が、データ d (1 ≤ d ≤ 100) のロックを試行していて待ち状態であることを表す。
ただし、入力は以下の条件を満たしていると仮定してよい。
- ロックされていないデータに対して、ユーザが待ち状態ではない。
- 二人以上のユーザにロックされているデータはない。
- ユーザ自身がロックしているデータに対して、待ち状態ではない。
- 同じ依存関係は与えられない。
出力
デッドロックが発生しているなら 1、発生していないなら 0 を１行に出力する。
入出力例
入力例１
4 1 lock 1 2 lock 2 1 wait 2 2 wait 1
出力例１
1
入力例２
4 3 lock 3 2 wait 3 3 lock 4 2 wait 4
出力例２
0