[原创]HDU 5326 work 【并查集】

[原创]HDU 5326 work 【并查集】

2016-02-29 22:44:31 Tabris_ 阅读数：307

---

博客爬取于2020-06-14 22:45:09
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50768959

---

Work

** Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1353    Accepted Submission(s): 813
**

Problem Description

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 Input

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

Sample Output

2

Author

题目大意就是求子集节点数是K的有几个

然后做着做着就出来了

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int has[2][105][105];

int son[105];

int n,m,sum;

int fin(int x)

{

   int num=0;

       for(int j=1; j<=n; j++)

       {

           if(has[1][x][j]==1&&has[0][x][j]==0)

           {

                num++;

                has[0][x][j]=1;

                son[x]+=fin(j);

           }

       }

   return son[x];

}

int main ()

{

   while(~scanf("%d%d",&n,&m))

    {

       memset(has,0,sizeof(has));

        memset(son,0,sizeof(son));

       int a,aa;

       sum=0;

       for(int i=1; i<n; i++)

       {

           scanf("%d%d",&a,&aa);

           has[1][a][aa]=1;

           son[a]++;

       }

       for(int i=1; i<=n; i++)

       {

           for(int j=1; j<=n; j++)

           {

               if(has[1][i][j]==1&&has[0][i][j]==0)

                {

                    has[0][i][j]=1;

                    son[i]+=fin(j);

                }

           }

       }

 

      /* for(int i=1; i<=n; i++)

       {

           printf("**%d\n",son[i]);

       }

 

       for(int i=1; i<=n; i++)

       {

           if(m==son[i])

                sum++;

       }

       printf("%d\n",sum);

    }

}*/

#include<stdio.h>

#include<string.h>

using namespace std;

int f[105];

int jihe[105];

void find2(int a)

{

   int r=a;

   while(f[r]!=r)

    {

       r=f[r];//r是一个上司。

       jihe[r]++;//这个上司有一个员工。

    }

}

int main()

{

   int n,m;

   while(~scanf("%d%d",&n,&m))

    {

       for(int i=1;i<=n;i++)

       {

           f[i]=i;

           jihe[i]=0;

       }

       for(int i=0;i<n-1;i++)

        {

           int x,y;

           scanf("%d%d",&x,&y);

           f[y]=x;//让并查集数组指向上司

       }

       int output=0;

       for(int i=1;i<=n;i++)

       {

           find2(i);//枚举每一个人，让他找他的上司

       }

       for(int i=1;i<=n;i++)

       {

            if(jihe[i]==m)

           output++;//符合条件的输出

       }

       printf("%d\n",output);

    }

}

 

//附几组数据

/*

7 6

1 2

1 3

2 4

2 5

3 6

3 7

 

7 2

1 2

1 3

2 4

2 5

3 6

3 7

 

7 2

7 6

7 5

6 4

6 3

5 2

5 1

 

7 1

1 2

2 3

3 4

4 5

5 6

6 7

*/