DFS序学习+例题
什么是DFS序?
DFS序就是指一棵树被DFS时所经过的节点的顺序
DFS序就是将树形结构转化为线性结构,用DFS遍历一遍这棵树,进入到x节点有一个in时间戳,递归退出时有一个out时间戳,x节点的两个时间戳之间遍历到的点,就是根为x的子树的所有节点。
时间戳
时间戳记录第一次开始访问这个点的时间和和最后结束访问的时间
void dfs(int s,int pre)
{
in[s]=++time;///进入时间
for(int i=head[s];i!=-1;i=load[i].p)
{
int e=load[i].e;
if(pre!=e)
dfs(e);
}
out[s]=time;///退出时间(时间不会+1)
}
特点
①将树形结构转换为线性结构,我们就可以利用线段树或者树状数组来进行维护
②每个叶子结点的区间都为一个点
③如果一个结点的时间戳为[L,R],那么更新这个点,直接更新L这个点。
④更新一个结点及其子树,更新这个结点时间戳的区间
例题 : POJ 3321
我是用线段树来写的,也可以用树状数组来解决。就是一道模板题。
代码:
///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const int mod=1e9+7;
const int INF=1e9;
int n,q;
struct node
{
int e;
int p;
}load[100005];
int head[100005],sign;
int time;
int in[100005];
int out[100005];
void add_edge(int s,int e)
{
load[++sign]=node{e,head[s]};
head[s]=sign;
}
void dfs(int s)
{
in[s]=++time;
for(int i=head[s];i!=-1;i=load[i].p)
dfs(load[i].e);
out[s]=time;
}
int root[400005];
void pushup(int sign)
{
root[sign]=root[sign<<1]+root[sign<<1|1];
}
void build_root(int sign,int l,int r)
{
if(l==r)
{
root[sign]=1;
return ;
}
int mid=(l+r)>>1;
build_root(sign<<1,l,mid);
build_root(sign<<1|1,mid+1,r);
pushup(sign);
}
void update_root(int sign,int l,int r,int x)
{
if(l==r)
{
root[sign]=1-root[sign];
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
update_root(sign<<1,l,mid,x);
else
update_root(sign<<1|1,mid+1,r,x);
pushup(sign);
}
int find_root(int sign,int l,int r,int a,int b)
{
if(l==a&&r==b)
return root[sign];
int mid=(l+r)>>1;
if(b<=mid)
return find_root(sign<<1,l,mid,a,b);
else if(a>mid)
return find_root(sign<<1|1,mid+1,r,a,b);
else
return find_root(sign<<1,l,mid,a,mid)+find_root(sign<<1|1,mid+1,r,mid+1,b);
}
void init()
{
time=sign=0;
memset(head,-1,sizeof(head));
}
int main()
{
int s,e;
init();
scanf("%d",&n);
build_root(1,1,n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&s,&e);
add_edge(s,e);
}
dfs(1);
scanf("%d",&q);
char c[3];
int x;
while(q--)
{
scanf("%s %d",c,&x);
if(c[0]=='Q')
printf("%d\n",find_root(1,1,n,in[x],out[x]));
else
update_root(1,1,n,in[x]);
}
return 0;
}