­

【Pet HDU – 4707 】【利用並查集找深度】

  • 2019 年 10 月 10 日
  • 筆記
#include<iostream>  #include<cstdio>  #include<cstring>  using namespace std;  const int maxn = 100000;  int T, N, D;  int x, y;  int f[maxn];  void init()  {      for(int i = 0; i <= N - 1; i++)          f[i] = i;  }  int Find(int root)  {      while(root != f[root])          root = f[root];      return root;  }  int Solve(int x)  {      int d = 0;      while(x != f[x])      {          x = f[x];          d++;      }      return d;  }  int main()  {      // freopen("input.txt", "r", stdin);      // freopen("output.txt", "w", stdout);      scanf("%d", &T);      while(T--)      {          scanf("%d %d", &N, &D);          init();          for(int i = 0; i < N - 1; i++)          {              scanf("%d %d", &x, &y);              f[y] = x;          }          int ans = 0;          for(int i = 0; i < N; i++)          {              if(Find(i) == 0)              {                  if(Solve(i) > D)                      ans++;              }          }          printf("%dn",ans);      }  }