专栏首页饶文津的专栏【CodeForces 699D】Fix a Tree

【CodeForces 699D】Fix a Tree

dfs找出联通块个数cnt,当形成环时,令指向已访问过节点的节点变成指向-1,即做一个标记。把它作为该联通图的根。

把所有联通的图变成一颗树,如果存在指向自己的点,那么它所在的联通块就是一个树(n-1条边),选择这样一个点,其它联通块的根指向它,就需要cnt-1次改变。如果都是环(没有指向自己的),那任意选定一个环,拆开,其它环拆开再连到此环上,就需要cnt次改变。

#include <cstdio>
#define N 200005
int a[N],v[N],h[N],fa[N],q[N],ans,cnt,ba;
int dfs(int u){
    v[u]=cnt;
    if(!v[a[u]])return a[u]=dfs(a[u])==-1?a[u]:a[a[u]];
    if(v[a[u]]==cnt&&a[u]!=u)return a[u]=-1;//指向的是本次dfs内访问的点,即形成环
    return a[u]=a[a[u]]==-1?a[u]:a[a[u]];//可能是-1即是前面的拆环点
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        fa[i]=a[i];
        if(a[i]==i)ba=i;
    }
    for(int i=1;i<=n;i++)
    if(!v[i]){
        cnt++;//第cnt次dfs
        dfs(i);
        if(++h[a[i]]==1)
            ans++;//联通块个数
    }
    printf("%d\n",ans-(ba>0));
    for(int i=1;i<=n;i++)
        //拆环点(-1),或者不是总根的树根,是需要改变的。
        if(a[i]==-1||i==a[i]&&i!=ba)printf("%d ",ba?ba:ba=i);//ba为0则选定i为总的根。
        else printf("%d ",fa[i]);//不改变
}
  

 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 1.5】SuperPrime Rib

    饶文津
  • 【POJ 1273】Drainage Ditches(网络流)

    一直不明白为什么我的耗时几百毫秒,明明差不多的程序啊,我改来改去还是几百毫秒。 ...一个小时后:明白了,原来把最大值0x3f(77)取0x3f3f3f3f就把...

    饶文津
  • 【USACO1.1】Broken Necklace

    一个环形项链,有rbw三种珠子,r代表red,b代表blue,w代表white,从任意一个位置断开,两端分别取珠子,同一端取的珠子要相同颜色,w可以染成想要的颜...

    饶文津
  • Splay详解(二)

    前言 在上一节中,我们讲述了Splay的核心操作rotate与splay 本节我会教大家如何用这两个函数实现各种强大的功能 为了方便讲解,我们拿这道题做例题...

    attack
  • 09年8月9日 ECUST ACM 练习赛总结

    B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位...

    owent
  • 洛谷P3391 【模板】文艺平衡树(Splay)

    题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

    attack
  • 洛谷P3224 [HNOI2012]永无乡

    题目描述 永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间...

    attack
  • Java--StringBuilder,StringBuffer,StringJoiner

    开始自己的一个半年计划,也就是java相关常用类的源码阅读,通过阅读查漏补缺,加深基础知识的运用与理解.

    屈定
  • 经典算法之bitmap算法

    本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...

    用户3467126
  • NOIP训练营内部试题-数数(树形DP+倍增)

    样例读入: 4 1 2 1 3 2 4 样例输出: 8 样例解释:

    用户5325900

扫码关注云+社区

领取腾讯云代金券