Deadlock

Time Limit : 1 sec, Memory Limit : 65536 KB

デッドロックを検出せよ

コンピュータにおける「データベース」とは、情報を管理するための入れ物で、「データベースマネジメントシステム(DBMS)」とは、その管理をする仕組みです。複数のユーザが利用するデータベースでは、DBMS は慎重に構築する必要があります。

例えば、倉庫から商品を1つ取り出した人が、データベースに対して以下の処理を行うとしましょう。
(1) 商品の個数 N をデータベースから読む。
(2) 新たな商品の個数 N-1 をデータベースに書き込む。

ユーザ1が(1)を終えて(2)を始める前に、別のユーザ2が倉庫から商品を取り出して(1)を行ったとします。ユーザ2もユーザ1と同じ個数を読むので、2人が(2)を終えたときには商品は2個減るのにデータベース上では1個しか減らないというおかしな結果になります。このような問題を防ぐために、DBMS は特定のデータを操作中のユーザに、そのデータを「ロック」する権利を与えます。ロックされていれば、他のユーザはその値を操作できなくなるので、おかしな結果を返すことはなくなります。

これで安全に操作できることは保証されますが、今度は別の問題が起こります。例えば、ユーザ1とユーザ2が以下のような順番でデータAとBをロックしようとしたらどうなるでしょうか?
(1) ユーザ1がデータAのロックを試みる → 成功(データAがロック中になる)
(2) ユーザ2がデータBのロックを試みる → 成功(データBがロック中になる)
(3) ユーザ1がデータBのロックを試みる → データBがロック中なのでユーザ1は待つ
(4) ユーザ2がデータAのロックを試みる → データAがロック中なのでユーザ2は待つ

(4)を実行した時点では、ユーザ1がA、ユーザ2がBをロックしているので、(3)(4)は永久に成功しませ ん。これを「デッドロック」と呼びます。DBMS はこれを検出しなければなりません。

ある時点でデッドロックが起きているかどうかは、その時点でのすべてのユーザとデータの依存関係を書き、循環ができているかどうかで判断できます。依存関係は,ユーザがデータをロック済みの場合はデータからユーザの向きに矢印を、ユーザがデータのロックを試行していて待ち状態になっている場合はユーザからデータの向きに矢印を書くことで表します。


上の(1)から(4)の例であれば、(4)を実行した時点での依存関係は右上のような図になります。このとき、矢印の方向に進むと、ユーザ1→データB→ユーザ2→データA→ユーザ1という循環ができているため、デッドロックが起きていることがわかります。DBMS の苦労を体験するため、あなたにここでやってもらいたいのは、このようなデッドロックを検出するプログラムを作成することです。

入力

入力は以下の形式で与えられる。

N
rel1
rel2
:
relN

1行目にユーザとデータの依存関係の数 N (1 ≤ N ≤ 1000) が与えられる。続く N 行に、ユーザとデータの依存関係 reli が与えられる。依存関係は lock と wait の2種類あり、各 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 を1行に出力する。

入出力例

入力例1

4
1 lock 1
2 lock 2
1 wait 2
2 wait 1

出力例1

1

入力例2

4
3 lock 3
2 wait 3
3 lock 4
2 wait 4

出力例2

0 

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/