hdu-2545

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/40535341

并查集的扩展应用，求节点到根的距离

//求节点到根的距离
//r[i]存储节点 i 到根的距离

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int p[100010];
int r[100010];

int findd (int x)
{
    int ans=0;
    while (x != p[x])
    {
        ans++;
        x=p[x];
    }
    return ans;
}

void un(int a ,int b)
{
    p[b]=a;
}

int main ()
{
    int n,m;
    int b,c;
    while (scanf ("%d%d",&n,&m)!=EOF)
    {
        if (n==0 && m==0)
            break;
        for (int i =0;i<=n;i++)
        {
            p[i]=i;
            r[i]=0;
        }

        for (int i =1;i<n;i++)
        {
            scanf ("%d%d",&b,&c);
            un(b,c);
        }

        for (int i =1;i<=m;i++)
        {
            scanf("%d %d",&b,&c);

            int t1=findd(b);
            int t2=findd(c);

            if (t1 <= t2)
                printf("lxh\n");
            else
                printf("pfz\n");
        }
    }
    return 0;
}