摘要
Title: 1977. 信息中继
Tag: 并查集、基环树
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1977. 信息中继

• 题意

  农夫约翰有 N 头奶牛，编号 1∼N。
  通过使用易拉罐和绳子构成的土制电话，它们会在约翰不注意的时候相互通信。
  每头奶牛最多可以将消息转发给另一头奶牛：
  对于奶牛 i，它会将自己收到的任何信息转发给奶牛 Fi（Fi 与 i 一定不同）。
  如果 Fi 为 0，则奶牛 i 不转发消息。
  不幸的是，奶牛们意识到来自某些奶牛的消息可能最终陷入循环之中，不断地被转发。
  请确定所有奶牛中有多少只奶牛发出的消息不会永远陷入循环之中。

• 思路

  由于点数有限，最后会生成基环树（点数=边数），那么就需要判断这个点的祖宗节点的父节点是否存在即可，若不存在，那么不会陷入循环

  ps: 还有一种思想是，只有和0相连的点，才不会陷入循环

• 代码

  import sys
  sys.setrecursionlimit(int(2e9))
  
  N = 1010
  
  p = [i for i in range(N)]
  f = [0] * N
  
  def find(x):
      if p[x] != x:
          p[x] = find(p[x])
      return p[x]
  
  
  n = int(input())
  for i in range(1, n + 1):
      f[i] = int(input())
      if f[i]:
          p[find(i)] = find(f[i])
  
  ans = 0
  for i in range(1, n + 1):
      r = find(i)
      if not f[r]:
          ans += 1
  
  print(ans)