【DFS】【树】【七中联考】【A】

136 阅读 0 评论 90 点赞

我是靠谱客的博主自觉芹菜，最近开发中收集的这篇文章主要介绍【DFS】【树】【七中联考】【A】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：
小A得到了一棵美丽的有根树。这棵树由n个节点以及n - 1条有向边构成，每条边都从父亲节点指向儿子节点，保证除了根节点以外的每个节点都有一个唯一的父亲。树上的节点从1到n标号。该树的一棵子树的定义为某个节点以及从该节点出发能够达到的所有节点的集合，显然这棵树共有n棵子树。小A认为一棵有根树是美丽的当且仅当这棵树内节点的标号构成了一个连续的整数区间。现在小A想知道这棵树上共有多少棵美丽的子树。
输入：
第一行有一个整数n，表示树的节点数。
接下来n–1行，每行两个整数u，v，表示存在一条从u到v的有向边。
输入保证该图是一棵有根树。
输出：
输出一个整数占一行，表示对应的答案。
样例输入：
4
2 3
2 1
2 4
样例输出：
4（原样例有误）
数据范围：
对于20%的数据，1 ≤ n ≤ 1000。
对于100%的数据，1 ≤ n ≤ 100000。
Solution:
不晓得为什么，这道题最后明明很简单的，但是我想了好久好久。。
所以打算好好理清一下思路：

目标：对于任意一个子树。判断一颗子树的所有节点，（包括该子树的根节点在内）是否为一段连续区间。

思路：假设现在求以k为根节点的子树是否满足题意。
连续区间：？？？
=> 区间必然存在最大值和最小值。
=>可以DFS得到每一个子树中的最大值最小值！
=>是否为连续区间？而且现在已经知道了区间的最大值最小值。
=>如果区间连续。则有以k为根节点的子树中，结点的总个数等于等于区间的长度！
所以有 num[k]=maxn[k]-minn[k]+1 则说明k子树的区间连续！
问题得到解决。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
#define LL long long 
using namespace std;
const int M=100005;
int head[M*2],cnt,fa[M*2],root,ans,maxn[M*2],minn[M*2],tot[M*2];
struct Edge{
    int to,next;
}edge[M*2];
int A[M*2],m,n,k,p,l,flag,a,b,c;
void read(int &n){
    char c=getchar();n=0;
    while(c<'0'||c>'9') {c=getchar();continue;}
    while(c>='0'&&c<='9'){n=n*10+c-'0';c=getchar();} 
}
void add(int from,int to){
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
void dfs1(int s,int f){
    tot[s]=1;
    maxn[s]=s;minn[s]=s;
    for (int i=head[s];i!=0;i=edge[i].next){
        int v=edge[i].to;
        if(v!=f){
            dfs1(v,s);
            tot[s]+=tot[v];
            maxn[s]=max(maxn[s],maxn[v]);
            maxn[s]=max(maxn[s],v);
            minn[s]=min(minn[s],minn[v]);
            minn[s]=min(minn[s],v);
        }
    }
}
int main()
{
    memset(maxn,0,sizeof(maxn));
    memset(minn,1000000007,sizeof(minn));
    read(n);
    for (int i=1;i<=n-1;i++){
        read(a);read(b);
        add(a,b);fa[b]=a;
    }
    for (int i=1;i<=n;i++)
        if(fa[i]==0){fa[i]=-1;root=i;break;}
    dfs1(root,-1);
    for (int i=1;i<=n;i++)
        if(maxn[i]-minn[i]+1==tot[i]) 
            ans++;
    printf("%d",ans);
    return 0;
}