ACM複習（9）8611 大牛之路I

Description 要成為ACM大牛，要掌握很多必需的知識點。某些知識點可以推導出别的知識點，是以在比賽中遇到的新問題，很多時候可以由你學過的知識中推導得到。現在給出要掌握的所有知識點數及知識點之間的推導關系。為了降低難度，假定知識的這種推導關系是單向的，即若A知識能直接（或間接）推導出B知識，那麼B知識是無法直接（或間接）推導出A知識的。一個新手想盡快掌握所有知識點，他至少需要掌握多少知識呢？

輸入格式 第一行0 < n <= 1000,0 < m < n*n.。n表示必需掌握的知識點數目，編号0~n-1。m為知識點間推導關系總數。接下來m行，每行A B兩個數，表示從A知識可以推導出B知識。

輸出格式 一個數x，表示最少要掌握的知識數。

輸入樣例

8 4

0 1

0 2

1 3

1 4

輸出樣例 4

解題思路

假設：

A 能推導的所有元素組成 A組

B 能推導的所有元素組成 B組

C D E… 依此類推

當A或A組某元素An可以推導元素M時，應将M歸入A組，此時将M的Boss設為A表明歸屬

某元素的Boss等于自己，說明該元素是組長

最後統計不同組長個數就可以了

#include<stdio.h>
int boss[];
int find(int n);
int main()
{
    int n, m, a, b, count = ;
    scanf("%d%d", &n, &m);
    for(int i = ; i < n; i ++)
        // 初始化所有元素的組長為自己
        boss[i] = i;
    for(int i = ; i < m; i ++)
    {
        scanf("%d %d", &a, &b);
        boss[b] = find(a);
    }
    for(int i = ; i < n; i ++)
        if(boss[i] == i)
            count ++;
    printf("%d\n", count);
    return ;
} 
int find(int n)
{
    // 找n所屬組的組長
    while(boss[n] != n)
        n = boss[n];
    return n;
}