codeforces 698B fix a tree 时间戳-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

codeforces 698B fix a tree 时间戳

阅读量：6197 次

发布时间：2019-06-21

本文共 823 字，大约阅读时间需要 2 分钟。

把一个父亲数组变成棵树的最小改动。

一想就只有环或者森林，用时间戳，每次爆搜就行，要么剖环，要么连树。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              using namespace std;int parent[200100];int time[200100];int cnt=0,st=0,ans=0;void fun(int root){ time[root]=++cnt; while (!time[parent[root]]) { time[root]=cnt; root=parent[root]; } if (time[parent[root]]==cnt)//环或者是单棵树 { if (st==0) st=root;//本身没有根，新建一个根 parent[root]=st;//剖环进已遍历的树或者新建树，单棵树亦同 } else ans--;}int main(){ int n; scanf ("%d",&n); for (int i=1;i<=n;i++) { scanf ("%d",&parent[i]); if (i==parent[i]) st=i; } for (int i=1;i<=n;i++) { if (!time[i]) fun(i),ans++; } printf ("%d\n",ans-1); for (int i=1;i

转载于:https://www.cnblogs.com/nj-czy/p/5695297.html

你可能感兴趣的文章

C++ 顺序容器(vector，list、deque,stack,queue)

【LeetCode每天一题】Flatten Binary Tree to Linked List(二叉树转化为单链表)

关于路由跟踪指令---traceroute

mycat实例（2）

Spring Boot干货系列：（一）优雅的入门篇

python学习笔记（十）常用模块

8.4、文件的处理、指针、锁定操作

布局与兼容性

Linux下SSH Session复制

关于httpservletrequest的获取真实的ip

Spring Boot的启动器Starter详解

Linux(Centos)中tcpdump参数用法详解（转）

异步并行批处理框架设计的一些思考（转）

查找正序排列的List中缺失的日期数据的一个算法

.NET MVC TempData、ViewData、ViewBag

（3.1）用ictclas4j进行中文分词，并去除停用词

[链接地址] Kibana汉化

去掉谷歌浏览器获取焦点时默认的input、textarea的边框和背景

JAVA自学笔记19

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-08 01:58:22 当前IP: 3.144.18.59 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我