专栏首页用户6093955的专栏【Pet HDU - 4707 】【利用并查集找深度】

【Pet HDU - 4707 】【利用并查集找深度】

#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("%d\n",ans);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • Dungeon Master POJ - 2251(bfs)

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 一遍记住Java常用的八种排序算法与代码实现

    对Java技术,架构技术感兴趣的同学,欢迎加QQ群668041364,一起学习,相互讨论。 群内已经有小伙伴将知识体系整理好(源码,笔记,PPT,学习视频),欢...

    java爱好者
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768

扫码关注云+社区

领取腾讯云代金券