树结构练习——判断给定森林中有多少棵树

小灰灰 2022-07-14 01:14 109阅读 0赞

### 树结构练习——判断给定森林中有多少棵树 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][] [ Statistic][Statistic]

#### Problem Description ####

众人皆知，在编程领域中，C++是一门非常重要的语言，不仅仅因为其强大的功能，还因为它是很多其他面向对象语言的祖先和典范。不过这世上几乎没什么东西是完美的，C++也不例外，多继承结构在带来强大功能的同时也给软件设计和维护带来了很多困难。为此，在java语言中，只允许单继承结构，并采用接口来模拟多继承。KK最近获得了一份java编写的迷你游戏的源代码，他对这份代码非常感兴趣。这份java代码是由n个类组成的（本题不考虑接口），现在，他想要知道这份代码中有多少个类没有直接基类。n个类分别用数字1..n表示。

#### Input ####

输入数据包含多组，每组数据格式如下。

第一行包含两个整数n,m，表示该份代码中的n个类和m个单继承关系。

后面m行，每行两个整数a b，表示a是b的直接基类。

#### Output ####

对于每组输入，输出该组数据中有多少个类没有直接基类。每组输出占一行。

#### Example Input ####

2 1
    1 2
    2 0

#### Example Output ####

1
    2

#### Hint ####

\#include <stdio.h>  
\#include <string.h>  
int pre\[123\];  
void initial(int n)  
\{  
for(int i=0;i<=n;i++)  
\{  
pre\[i\] = i;  
\}  
\}  
  
  
int Find(int root)  
\{  
int a = root;  
while(root!=pre\[root\])  
\{  
root = pre\[root\];  
\}  
while(pre\[a\]!=root)  
\{  
int temp = pre\[a\];  
pre\[a\] = root;  
a = temp;  
\}  
return root;  
\}  
int Count(int n)  
\{  
int count=0;  
for(int i=0;i<=n;i++)  
\{  
int root = Find(i);  
if(root)  
\{  
count++;  
pre\[root\] = 0;  
\}  
\}  
return count;  
\}  
void Join(int a,int b)  
\{  
int root\_a = Find(a);  
int root\_b = Find(b);  
if(root\_a!=root\_b)  
\{  
if(root\_a<root\_b)  
\{  
pre\[root\_a\] = root\_b;  
\}  
else  
\{  
pre\[root\_b\] = root\_a;  
\}  
\}  
\}  
int main()  
\{  
int n,m;  
while(~scanf("%d%d",&n,&m))  
\{  
initial(n);  
while(m--)  
\{  
int u,v;  
scanf("%d%d",&u,&v);  
Join(u,v);  
\}  
printf("%d\\n",Count(n));  
\}  
return 0;  
\}

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1907/pid/2129.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1907/pid/2129.html