《算法竞赛进阶指南》创世纪

B-创世纪_0x64 图论-基环树

https://ac.nowcoder.com/acm/contest/1058/B

这道题是个基环树DP的题目所以我们先开始了解基环树

基环树是什么？

基环树是一种图，它由一个环组成，环上每个点都是一棵树点树根，所以称为基环树。当然，一棵树上连一条边也会变成基环树。

基环树分为两大类：有向基环树，无向基环树

有向基环树又分为：
基环内向树：每个点出度为1（因此每个环上点的子树，儿子指向父亲）

基环外向树：每个点入度为1（因此每个环上点的子树，父亲指向儿子）

无向基环树

有向基环树如图为内向基环树看上去是以环为中心其它向环内缩外向树反之

[以上两图来源于网络]

重点

对于与基环树有关的题目来讲找到环是首要的任务（当然了你得先找到根）

无向图

一般通过DFS的方式寻找环
本质上就是不断的寻找直到找到之前找过的点

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=100010; 
struct node{
    int v,nxt;
}e[MAXN<<1];
int head[MAXN],tot;
int fa[MAXN],dfn[MAXN],idx;//dfs序 便于寻找访问关系 
int loop[MAXN],cnt;//环的编号 定义：一个环才叫基环树 
inline void add(int x,int y)
{
    tot++;
    e[tot].v = y;
    e[tot].nxt = head[x];
    head[x] = tot;
}
inline void get_loop(int u)
{
    dfn[u]=++idx;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa[u])
        {
            continue;//这是父亲 
        }
        if(dfn[v])//这个点访问过   !!!就是找到环了!!! 
        {
            if(dfn[v]<dfn[u])
            {
                continue;//退回起点 
            }
            //找到起点了
            loop[++cnt]=v;
            for(;v!=u;v=fa[v])
                loop[++cnt]=fa[v];
        }
        else //没访问过
        {
            fa[v]=u;
            get_loop(v);    
        } 
    }
}
int n,a,b;
//找到的环按dfn降序排 
//环内一个点必然与另外两个点相邻 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a>>b,add(a,b),add(b,a);
    get_loop(1);
//    for(int i=1;i<=n;i++) cout<<dfn[i]<<endl;
    for(int i=1;i<=cnt;i++) cout<<loop[i]<<" ";
}

模板题：https://www.dotcpp.com/oj/problem1841.html

有向图

如果只是判断有无环可以使用拓扑排序，拓扑排序的存在条件是没有环，如果拓扑排序不能完成那就是有环。

使用dfs保存环，如果模板不进行改变的话遇到下面这张情况就会造成当场凉凉的局面

当你过2->3->4->5后再返回2的时候你会再去寻找6->4并且惊奇的发现4的dfn比6小于是程序会惊呼“这里有个环！”但是聪明的你会发现这个点访是访问过，但是他并不是个环。

所以算法需要改变。
图片说明

struct node{int v,nxt;}e[maxn];
int head[maxn],tot;
inline void add(int x,int y){
    tot++;
    e[tot].v =y;
    e[tot].nxt =head[x];
    head[x]=tot;
}
int n,a,cnt;
/*
    v--> 0没去过 
         1在里面 
        -1去完了 
*/
int vis[maxn],path[maxn],loop[maxn],tis;
inline void get_loop(int u){
    vis[u]=1;
    path[++tis]=u;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v ;
        if(vis[v]==0) get_loop(v);
        if(vis[v]==1)
        {
            for(int j=tis;;j--)
            {
                loop[++cnt]=path[j];//逆序 后头的在环的前面 
                if(path[j]==v) break; 
            }
        }
        if(vis[v]==-1) continue;//去过了 
    }
    vis[u]=-1;
    tis--; 
}

模板题链接NOIP2015：https://ac.nowcoder.com/acm/contest/263/E

要点

有些题目赤裸裸的就告诉你，“给出一棵基环树（环套树）”，但是有的题会有一些标志。比如说n个点n条边（即n种关系），甚至有的题用更隐晦的手法来描写n个点n条边。

而n个点一定会涉及的就是环，所以找环这个模板是非常重要的当会了找环后你就可以对这棵树使用dp的加成方式来解题

接下来就是题解了

请先浏览题目……

可以发现从被限制节点向限制节点连一条有向边，可以构成一张内向树森林，这里特别提出判环的另一种方式，使用并查集，这里的特点是并查集只可以查找到这个环的一处，如果需要查找整个环那就只有前面页讲到的模板了。

使用并查集找到某一颗树后，我们可以做出如下思考：我们先暂时遗忘他有环这个恼火的条件，当x节点需要放的时候，那么他至少有一个儿子不可以放，所以用g代表不放，f代表放列出柿子：

图片说明

此时我们惊讶的发现这就是没有上司的舞会的技巧呀！

于是我们可以开始考虑那个恼火的环了

我们可以想到的是，在一个环上，对于一个节点来讲，他本人只有在和不在两种选项，所以我们可以通过条件语句的改变，进行两次dfs，一次断开，一次强行连上，比较哪一个更大，问题便迎刃而解。

这里提出注意事项：在第一个dfs中我们对f是强行负值，这样对于一些叶子节点来讲t值是没有更改的，这就导致f值在最后是一个极小值，这样的f是不会更新答案的。如果不写第一个dfs，使得一些在本不能更新答案的点更新了答案，导致答案错误。所以第一个dfs是必要的。

然后再输出最终的答案，这道烦爆了的题就A掉了，而且你还掌握了将基环树DP变为两次树形DP的这种操作。

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#define LL long long
#define debug cout<<"bug"<<endl;
using namespace std;
const int maxn=1000010;
inline void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=f;}
struct node{int v,nxt;}e[maxn];
int head[maxn],tot;
inline void add(int x,int y){
    tot++;
    e[tot].v =y;
    e[tot].nxt =head[x];
    head[x]=tot;
}
int n,a,cnt,ra[maxn],rb[maxn],now;

int fa[maxn];
inline int find(int x)
{
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}

int f[maxn],g[maxn];//f 放 g 不放 
inline void dfs(int x)
{
    int t=1<<30;
    g[x]=0;
    for(int i=head[x];i;i=e[i].nxt )
    {
        int v=e[i].v ;
        if(v!=now)
            dfs(v);
        g[x]+=max(g[v],f[v]);
        t=min(t, max(g[v],f[v])-g[v] ); //没有上司的舞会中的技巧 
    }
    f[x]=g[x]+1-t;
}
int main()
{
    int ans=0;
    read(n);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        read(a);
        if(find(a)!=find(i))
        {
            add(a,i);
            fa[fa[a]]=fa[i];
        }
        else
        {
            cnt++,ra[cnt]=a,rb[cnt]=i;//本身在环上是不连通的 
        }
    } 
    for(int i=1;i<=cnt;i++)//森林 
    {
        dfs(ra[i]);
        now=ra[i];//断环 
        dfs(rb[i]),a=f[rb[i]];//在这一轮的dfs中是不会去更新 ra[i]儿子的f g值的，导致本身没有ra[i]的值也是没有的，所以需要上一个提前处理出来 
        f[ra[i]]=g[ra[i]]+1;//强行链接 （在max中程序一定会选择f，它本身的限制节点rb[i]不会被选中 所以有限制他的充分条件） 
        dfs(rb[i]), ans+=max(g[rb[i]],a);
    }
    printf("%d",ans);
    return 0;
}

最后同类型题目骑士推荐一做：https://www.luogu.org/problem/P2607