欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Work

程序员文章站 2022-07-11 10:39:09
...

Problem Description

Work


It’s an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company.
As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A’s title is higher than B(A is the direct or indirect leader of B), we call it A manages B.
Now, give you the relation of a company, can you calculate how many people manage k people. 

Input

There are multiple test cases. Each test case begins with two integers n and k, n indicates the number of stuff of the company. Each of the following n-1 lines has two integers A and B, means A is the direct leader of B. 1 <= n <= 100 , 0 <= k < n 1 <= A, B <= n

Output

For each test case, output the answer as described above.

Sample Inpu

7 2 1 2 1 3 2 4 2 5 3 6 3 7

Sample Output

2

Author

ZSTU

Source

2015 Multi-University Training Contest 3

题目大概:

给出n个人和(n-1)个关系,a b表示a 是 b的领导。然后,求有k个下属的人的数量。

思路:

本来想用并查集,然后随便改了改,改的也不是路径压缩了,交了一发,过了,看来这份题的出题人比较良心。。。

代码:

#include <bits/stdc++.h>

using namespace std;
const int maxn=110;
int fa[maxn],shu[maxn];
struct poin
{
    int u,v;
}G[maxn];
int cmp(poin a,poin b)
{
    return a.u>b.u;
}
int f(int x)
{
    if(fa[x]==-1)return x;
    else return fa[x]=f(fa[x]);
}
void bond(int x,int y)
{
    int fx=f(x);
    int fy=f(y);
    if(fx!=fy)
    {
        fa[fy]=fx;
        shu[x]+=shu[y]+1;
        //cout<<x<<" "<<y<<" "<<shu[fx]<<endl;
    }
}
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        memset(fa,-1,sizeof(fa));
        for(int i=1;i<=n;i++)shu[i]=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&G[i].u,&G[i].v);
        }
        sort(G+1,G+n,cmp);
        for(int i=1;i<n;i++)
        {
            bond(G[i].u,G[i].v);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(shu[i]==k)ans++;
            //cout<<shu[i]<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}