755C - PolandBall and Forest

ゞ浴缸里的玫瑰 2022-07-14 17:40 110阅读 0赞

## 题意 ##

有n个结点，分布在数量未知的树上，也就是说这些树可能是一个森林。  
现在给出每个点在各自树上的最远点，如果有多个最远点的话，那就给出id编号最小的那一个点。

## 思路1 ##

直接无脑并查集

#include<iostream>
    using namespace std;
    int parent[100005];
    int find(int x)      
    {
        return x==parent[x]?x:find(parent[x]);
    }
    
    void Union(int a,int b)     
    {
        int x=find(parent[a]);    
        int y=find(parent[b]);    
        if(x!=y)
          parent[x]=y;     
    }
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            int a,sum=0;
            for(int i=1;i<=n;i++)
              parent[i]=i;            
            for(int i=1;i<=n;i++)
            {
                cin>>a;
                Union(i,a);           
            }
            for(int i=1;i<=n;i++)
                if(parent[i]==i)         
                  sum++; 
            cout<<sum<<endl; 
        }
        return 0;
    }

## 思路2 ##

我猜测思路2才是题者想要的解法？

对于每一个结点，如果它的最远点的最远点是自己本身，则这两个点是树上的两端结点最小的直径，也可以认为是某个树的标示。

记录这样的直径的个数就是树的个数。

# -*- coding: utf-8 -*-
    # @Author: HaonanWu
    # @Date: 2017-03-02 10:14:55
    # @Last Modified by: HaonanWu
    # @Last Modified time: 2017-03-02 10:45:15
    
    n = int(input())
    p = [0]+list(map(int,input().split()))
    d = set()
    for i in range(1,n+1):
        if p[p[i]] == i:
            d.add(min(i,p[i]))
    print(len(d))

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关 forest框架代理设置

forest框架通过配置文件实现代理

柔光的暖阳◎/ 2024年04月25日 08:40/ 0 赞/ 58 阅读

相关 Delete Nodes And Return Forest（C++删点成林）

解题思路：（1）后序遍历，将删除节点置空（2）存储删除节点的左右子节点 / Definition for a binary tree node.

阳光穿透心脏的1/2处/ 2023年01月06日 05:45/ 0 赞/ 61 阅读

相关 Forest介绍

前言本篇栏目主要和大家分享我对国内一款开源框架Forest的一些研究学习文章。如果大家也在对他感兴趣，并且对他底层实现有一定的好奇，希望我的这个栏目文章可以给到大家

╰+攻爆jí腚メ/ 2022年09月11日 03:22/ 0 赞/ 14 阅读

相关 NYOJ-755山谷【模拟】

山谷时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述八百里伏牛山连绵不断，高低起伏。家住山脚下的小明开始学习识数了，面朝群山，

矫情吗；*/ 2022年08月14日 04:56/ 0 赞/ 27 阅读

相关 A Brief Tour of the Trees and Forests

[A Brief Tour of the Trees and Forests][] Tree methods such as CART (classificati

绝地灬酷狼/ 2022年07月29日 10:50/ 0 赞/ 145 阅读

相关 Random Forests (随机森林）

在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的

古城微笑少年丶/ 2022年07月28日 10:51/ 0 赞/ 260 阅读

相关 755C - PolandBall and Forest

题意有n个结点，分布在数量未知的树上，也就是说这些树可能是一个森林。现在给出每个点在各自树上的最远点，如果有多个最远点的话，那就给出id编号最小的那一个点。

ゞ浴缸里的玫瑰/ 2022年07月14日 17:40/ 0 赞/ 111 阅读

相关 A Brief Tour of the Trees and Forests

Tree methods such as CART (classification and regression trees) can be used as alternati

谁借莪１个温暖的怀抱￠/ 2022年07月11日 01:41/ 0 赞/ 267 阅读

相关 Random Forest算法简介

转自JoinQuant量化课堂一、相关概念分类器：分类器就是给定一个样本的数据，判定这个样本属于哪个类别的算法。例如在股票涨跌预测中，我们认为前一天的交易量和收盘价对

短命女/ 2022年06月17日 03:39/ 0 赞/ 209 阅读

相关 sudo chmod 755 ....指令分析

sudo：使用管理员root权限执行指令。 chmod：文件调用权限分为三级 : 文件拥有者、群组、其他。利用 chmod可以改变文件权限。 775：7，7，5各代表一个权

川长思鸟来/ 2022年03月02日 00:56/ 0 赞/ 889 阅读