SCAU 8618 大牛之路II （并查集）

8618 大牛之路II

时间限制:500MS  内存限制:1000K
提交次数:28 通过次数:4

题型: 编程题   语言: 无限制

 

Description

要成为ACM大牛，要掌握很多必需的知识点。某些知识点可以推导出别的知识点，所以在比赛中遇到的新问题，很多时候可以由你学过的知识中推导得到。现在给出要掌握的所有知识点数及知识点之间的推导关系。注意，若A知识可以直接（间接）推导出B知识，B知识也是有可能直接（间接）推导出A知识的。一个新手想尽快具有解决所有知识点的能力，他至少需要掌握多少知识呢？ 

Input

多组数据，每组数据格式为： 第一行1<=n<=18,0<=m<=n*n.。n表示必需掌握的知识点数目，编号0~n-1。m为知识点间推导关系总数。接下来m行，每行A B两个数，表示从A知识可以推导出B知识。 当n==0 && m==0时，结束程序。两个Case间有一空行。

Output

一个数x，表示最少要掌握的知识数。

 

Sample Input

8 4
0 1
0 2
1 3
1 4

2 2
0 1
1 0

0 0

 

Sample Output

4
1

 

Source

Wizard

 

Provider

admin

#include<stdio.h>
#include<string.h>

//father[]数组存储祖先/父亲的节点，flag[]数组作为哨兵，0表示i的父亲为本身，
//1表示i已有父亲或祖先（除自身外）【flag[]是根据题目的意思设定】
 
int father[20],flag[20]; 

int find(int k)
{// 查找x元素所在的集合,回溯时压缩路径 
    return father[k] == k ? k : (father[k] = find(father[k]));
}

int main()
{
    int n, m, i, a, b, cnt = 0;
    while(scanf("%d %d", &n, &m) == 2 && (n || m))
    {
        cnt = 0;
        memset(flag, 0, sizeof(flag));
        // 初始化集合 
        for(i=0; i<n; i++)    father[i] = i;
        for(i=0; i<m; i++)
        {
            scanf("%d %d", &a, &b);
            if(flag[b]) continue;  
             flag[b] = 1;
             // 合并集合 
             a = find(a);
             b = find(b);
            if(a != b) father[b] = a; 
        }
        
        for(i=0; i<n; i++)
            if(father[i] == i) cnt++;
        printf("%d\n", cnt);
    }
    
    return 0;
}