Problem:


Problem B: Let's JUMPSTYLE

Description

踊りの好きなFは，とあるダンスホールでJUMPSTYLEと呼ばれるハードコアな踊りの練習をすることにした．

フロアはN×Nの格子状にタイルが敷き詰められている．
踊りの練習をサポートするため，各タイルには次のステップに飛び移るべきタイルの座標が書かれている．Fは日々の練習によって強靭な運動神経を持っており，フロア内の任意のタイルへ飛び移ることができる．

Fは，十分に長い時間この踊りを続けていけば，いつか定常状態に入り，同じルートをただループする状態になることに気付いた．Fはこのようなループがこのフロアにいくつ存在するのか疑問に思い，プログラマであるあなたに相談することにした．

Input

入力は複数のテストケースから成る．

各テストケースはフロアの1辺の長さNを含む1行で始まる．(1 ≦ N ≦ 100)

続くN行は，フロアの各タイルに書いてあるジャンプ先の座標を以下のように表している．

 は，それぞれ座標(i, j)にあるタイルに書いてあるジャンプ先のx座標およびy座標を表す．座標は0-originであり，すべての座標の値は0以上N未満の整数である．

入力は0のみから成る行で終わる．

Output

各テストケースに対し，異なるループの個数を1行で出力する．

Sample Input

1
0 0
2
1 1 0 1
1 0 0 0
2
1 1 0 1
1 1 1 0
3
0 1 2 2 2 1
0 2 1 2 2 1
0 0 0 1 1 1
4
3 2 2 0 3 2 2 1
1 1 0 3 1 1 3 1
0 3 2 3 3 0 2 3
1 1 1 1 3 2 1 3
0

Output for Sample Input

1
2
1
2
3



Sample input:
1
0 0
2
1 1 0 1
1 0 0 0
2
1 1 0 1
1 1 1 0
3
0 1 2 2 2 1
0 2 1 2 2 1
0 0 0 1 1 1
4
3 2 2 0 3 2 2 1
1 1 0 3 1 1 3 1
0 3 2 3 3 0 2 3
1 1 1 1 3 2 1 3
0


Sample output:
1
2
1
2
3

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  to = []
  fr = [[] for _ in range(n * n)]
  for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
      x, y = line[2 * j:2 * j + 2]
      to.append(y * n + x)
      fr[y * n + x].append(i * n + j)
  
  order = []
  used = [False] * (n * n)
  def dfs(x):
    if used[x]:return
    used[x] = True
    dfs(to[x])
    order.append(x)
  
  for i in range(n * n):
    dfs(i)
  
  def dfs2(x, used, group):
    if used[x]:return
    used[x] = True
    for f in fr[x]:
      dfs2(f, used, group)
    group.append(x)
  
  used = [False] * (n * n)
  ans = 0
  for i in order:
    group = []
    if not used[i]:
      dfs2(i, used, group)
    if len(group) >= 1:
      ans += 1
  print(ans)

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  to = []
  fr = [[] for _ in range(n * n)]
  for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
      x, y = line[2 * j:2 * j + 2]
      to.append(y * n + x)
      fr[y * n + x].append(i * n + j)
  
  order = []
  used = [False] * (n * n)
  def dfs(x):
    if used[x]:return
    used[x] = True
    dfs(to[x])
    order.append(x)
  
  for i in range(n * n):
    dfs(i)
  order.reverse()
  
  def dfs2(x, used, group):
    if used[x]:return False
    if x in group:return True
    group.append(x)
    ret = False
    ret = ret or dfs2(to[x], used, group)
    return ret
  
  used = [False] * (n * n)
  ans = 0
  for i in order:
    group = []
    if not used[i]:
      if dfs2(i, used, group):ans += 1
    for g in group:used[g] = True
  print(ans)

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  to = []
  for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
      x, y = line[2 * j:2 * j + 2]
      to.append(y * n + x)
  
  order = []
  used = [False] * (n * n)
  def dfs(x):
    if used[x]:return
    used[x] = True
    dfs(to[x])
    order.append(x)
  
  for i in range(n * n):
    dfs(i)
  order.reverse()
  
  def dfs2(x, used, group):
    if used[x]:return False
    if x in group:return True
    group.add(x)
    return dfs2(to[x], used, group)
  
  used = [False] * (n * n)
  ans = 0
  for i in order:
    group = set()
    if not used[i]:
      if dfs2(i, used, group):ans += 1
    for g in group:used[g] = True
  print(ans)

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  to = []
  for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
      x, y = line[2 * j:2 * j + 2]
      to.append(y * n + x)
  
  order = []
  used = [False] * (n * n)
  def dfs(x):
    if used[x]:return
    used[x] = True
    dfs(to[x])
    order.append(x)
  
  for i in range(n * n):
    dfs(i)
  order.reverse()
  
  def dfs2(x, used, group):
    if x in group:return True
    if used[x]:return False
    group.add(x)
    used[x] = True
    return dfs2(to[x], used, group)
  
  used = [False] * (n * n)
  ans = 0
  for i in order:
    group = set()
    if not used[i]:
      if dfs2(i, used, group):ans += 1
  print(ans)

Submission status: Accepted

Solution code:
while True:
  N = int(raw_input())

  if N == 0:
    break

  field = [[(0, 0) for x in xrange(N)] for y in xrange(N)]

  for y in xrange(N):
    line = map(int, raw_input().split())

    for x in xrange(N):
      field[y][x] = (line[2 * x + 1], line[2 * x])

  vis = set()

  cnt = 0

  for y in xrange(N):
    for x in xrange(N):

      cur = (y, x)

      if cur in vis: continue

      loop = set()
      loop.add(cur)

      while True:
        cur = field[cur[0]][cur[1]]

        if cur in vis:
          loop.add(cur)
          vis = vis | loop
          break

        if cur in loop:
          loop.add(cur)
          cnt += 1
          vis = vis | loop
          break

        loop.add(cur)
  print cnt