POJ 5326 - Work

Problem - 5326

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

这个题目是个递推，不过由于是树形的，需要dfs来完成递推的过程。
关键在于p[now] += p[to]+1;如果now能manage to的话。

此处采用链式前向星来保存关系图。
http://blog.csdn.net/tc_to_top/article/details/47108595

1. struct EDGE  
2. {  
3.     int v, next;  
4. }e[MAX];  
5. int head[MAX], num[MAX];  
6. bool in[MAX], vis[MAX];  
7. int cnt, ans;  
8. int n, k;  
9.   
10. void Add(int u, int v)  
11. {  
12.     e[cnt].v = v;  
13.     e[cnt].next = head[u];  
14.     head[u] = cnt ++;  
15. }  
16.   
17. void DFS(int u)  
18. {  
19.     vis[u] = true;  
20.     num[u] = 0;  
21.     for(int i = head[u]; i != -1; i = e[i].next)  
22.     {  
23.         int v = e[i].v;  
24.         if(!vis[v])  
25.         {  
26.             DFS(v);  
27.             num[u] += (num[v] + 1);  
28.         }  
29.     }  
30.     if(num[u] == k)  
31.         ans ++;  
32.     return;  
33. }  
34.   
35. int main()  
36. {  
37.     while(scanf("%d %d", &n, &k) != EOF)  
38.     {  
39.         cnt = 0;  
40.         ans = 0;  
41.         memset(head, -1, sizeof(head));  
42.         memset(in, false, sizeof(in));  
43.         memset(vis, false, sizeof(vis));  
44.         for(int i = 0; i < n - 1; i++)  
45.         {  
46.             int u, v;  
47.             scanf("%d %d", &u, &v);  
48.             Add(u, v);  
49.             in[v] ++;  
50.         }  
51.         for(int i = 1; i <= n; i++)  
52.             if(in[i] == 0)  
53.                 DFS(i);  
54.         printf("%d\n", ans);  
55.     }  
56. }  

X. DFS + DP

http://blog.csdn.net/firenet1/article/details/47129831

1. vector<int>haha[200];  
2. int check[200];  
3. int num[200];  
4. int dfs(int u){  
5.     if(check[u]) return num[u]+1;  
6.     check[u] = 1;  
7.     for(int i = 0; i < haha[u].size();i++)  
8.         num[u] += dfs(haha[u][i]);  
9.     return num[u]+1;  
10. }  
11.   
12.   
13. int main(){  
14.     int n,k;  
15.     while(scanf("%d%d",&n,&k)!=EOF){  
16.         for(int i = 0;i <= n; i++)  
17.             haha[i].clear();  
18.         int u,v;  
19.         for(int i =1;i < n; i++){  
20.             scanf("%d%d",&u,&v);  
21.             haha[u].push_back(v);  
22.         }  
23.         memset(check,0,sizeof(check));  
24.         memset(num,0,sizeof(num));  
25.         int ans = 0;  
26.         for(int i = 1;i <= n; i++){  
27.   
28.             if(check[i]) continue;  
29.             dfs(i);  
30.         }  
31.         for(int i =1;i <= n; i++)  
32.             if(num[i]==k) ans++;  
33.         cout<<ans<<endl;  
34.     }  
35.     return 0;  
36. } 

http://www.cnblogs.com/qq-star/p/4686536.html

int dfs(int x)
10 {
11     int sum=0;
12     for (int i=1;i<=n;i++)
13     {
14         if (Map[x][i]==1)
15         {
16             sum++;
17             sum+=dfs(i);
18         }
19     }
20     return sum;
21 }
22 
23 int main()
24 {
25     int a,b,ans;
26     while (~scanf("%d%d",&n,&m))
27     {
28         ans=0;
29         memset(Map,0,sizeof(Map));
30         //memset(ok,0,sizeof(ok));
31         for (int i=1; i<=n-1; i++)
32         {
33             scanf("%d%d",&a,&b);
34             Map[a][b]=1;
35         }
36         for (int i=1;i<=n;i++)
37         {
38             if (dfs(i)==m)
39                 ans++;
40         }
41         printf ("%d\n",ans);
42     }
43     return 0;
44 }

X. Reclusive solution - not efficient
http://www.zgxue.com/198/1980697.html

struct node
{
 int num,s[105];
}res[105];
int ans;
void judge(int i)
{
 if(res[i].num==0)
     return ;
 ans+=res[i].num;
 for(int j=0;j<res[i].num;j++)
     judge(res[i].s[j]);
}
int main()
{
 int n,k,a,b,cnt;
 while(~scanf("%d%d",&n,&k))
 {
  memset(res,0,sizeof(res));
  for(int i=0;i<n-1;i++)
  {
   scanf("%d%d",&a,&b);
   res[a].s[res[a].num]=b;
   res[a].num++;
  }
  cnt=0;
  for(int i=1;i<=n;i++)
  {
   ans=res[i].num;
   for(int j=0;j<res[i].num;j++)
       judge(res[i].s[j]);
            if(ans==k)
                cnt++;
  }
  printf("%d\n",cnt);
 }
 return 0;
}

Read full article from Problem - 5326