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

喜欢ヅ旅行 2022-07-19 11:54 95阅读 0赞

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

####  ####

#### Time Limit: 1000MS Memory limit: 65536K ####

## 题目描述 ##

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

## 输入 ##

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

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

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

## 输出 ##

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

## 示例输入 ##

2 1
    1 2
    2 0

## 示例输出 ##

1
    2

## 提示 ##

此题跟求连通分量的个数是一样的，只要找出有几个根节点就有多少棵树，主要通过判断顶点的pre值是否改变

#include<cstdio>
    using namespace std;
    
    int pre[1000];//记录顶点的上一级顶点值
    int n,m;//这个地方定义n,m时候，不要放在pre[]数组上面，不然wrong anser（可以放在这定义，也可以放在main函数中）
    
    //由子节点寻找根节点
    int findroot(int x)
    {
        int r=x;
        while(pre[r]!=r)//循环直到找到根节点
        {
            r=pre[r];
        }
    
        int i=x,j;
        while(pre[i]!=r)//路径压缩，多级关系变成二级关系
        {
            j=pre[i];
            pre[i]=r;
            i=j;
        }
        return r;
    }
    
    //将多个分量的根节点合并成一个根节点
    void combination(int x,int y)
    {
        int fx=findroot(x);
        int fy=findroot(y);
        if(fx>fy)
        {
            pre[fy]=fx;
        }
        else
        {
            pre[fx]=fy;
        }
    }
    
    int main()
    {
        int t;
        while(~scanf("%d %d",&n,&m))
        {
            int count=0;
            for(int i=1;i<=n;i++)//将每个顶点的上一级全部初始化自身值
            {
                pre[i]=i;
            }
            int a,b;
            for(int i=0;i<m;i++)
            {
                scanf("%d %d",&a,&b);
                if(findroot(a)!=findroot(b))
                {
                    pre[findroot(a)]=b;
                }
            }
    
            for(int i=1;i<=n;i++)
            {
                if(pre[i]==i)//顶点为根节点
                {
                    count++;
                }
            }
            printf("%d\n",count);
        }
        return 0;
    }