《算法竞赛进阶指南》0x21树与图的遍历

树与图的深度优先遍历，树的dfs序，深度和重心

树的深度优先遍历，就是在每个点x上面对多条分支时，任意选一条边走下去，执行递归，直到回溯至点x后，再考虑走其他的边。

void dfs(int x)
{v[x]=1;//记录点x被访问过for(int i=head[x];i;i=ne[i]){int y=ver[i];if(v[y])continue;//点有、被访问过 dfs(y);} 
}

树的dfs序
一般来讲，我们对树进行深度优先遍历时，对于每个节点，在刚进入递归后以及即将进入递归前各记录一次该点的编号，最后产生的长度为2n的节点序列就是树的dfs序。

void dfs(int x)
{a[++m]=x;//a数组存储DFS序v[x]=1;//记录点x被访问过 for(int i=head[x];i;i=ne[i]){int y=ver[i];if(v[y])continue;dfs(y);} a[++m]=x; 
}

DFS序的特点：每个节点x的编号在序列中恰好出现两次。设这两次出现的位置为L[x]和R[x]，那么区间[L[x],R[x]]就是以x为根的子树的DFS序。

树的深度
树中各个节点的深度是一种自上而下的统计信息。起初我们已知根节点的深度为0。若节点x的深度为d[x],则它的子节点y的深度就是d[y]=d[x]+1。

void dfs(int x)
{v[x]=1;for(int i=head[x];i;i=ne[i]){int y=ver[i];if(v[y])continue;d[y]=d[x]+1;//从父结点x到子节点y递推，计算深度 dfs(y);}
} 

树的重心
有很多信息是自下而上统计的，比如每个节点x为根的子树大小size[x]。若节点x的根节点为y1，y2，…yn，则size[x]=size[y1]+size[y2]+…+size[yn]+1。
对于一个节点x，如果我们把它从树中删除，那么原来一棵树可能会被分成若干个不相连的部分，其中每一部分都是一棵子树。设max_part(x)表示在删除节点x后产生的子树中最大的一棵的大小。使max_part函数取到最小值的节点p就称为整棵树的重心。

void dfs(int x)
{v[x]=1,size[x]=1;//子树x的大小 int max_part=0;//删除x后分成的最大子树的大小 for(int i=x;i;i=ne[i]){int y=ver[i];if(v[y])continue;//点y已经访问过了 dfs(y);size[x]+=size[y];//从子节点向父节点递推 max_part=max(max_part,size[y]);//n为整棵树节点数目 }max_part=max(max_part,n-size[x]);if(max_part<ans){ans=max_part;//全局变量ans记录重心对应的max_part的值 pos=x;//全局变量pos记录了重心 }
} 

图的连通块划分
对一个森林进行深度优先遍历，可以划分出森林里的每棵树。

void dfs(int x)
{v[x]=cnt;for(int i=1;i;i=ne[i]){int y=ver[i];if(v[y])continue;dfs(y);}
}
for(int i=1;i<=n;i++)
{if(v[i])continue;cnt++;dfs(i);
}

树与图的广度优先遍历，拓扑排序

树与图的广度优先遍历需要使用一个队列来实现。起初队列中包含一个起点。在广度优先遍历的过程中，不断从队头取出一个节点x，对于x面对的多条分支，把沿着每条分支到达的下一个节点插入队尾。

void bfs()
{memset(d,0,sizeof d);queue<int>q;q.push(1),d[1]=1;while(q.size()>0){int x=q.front();q.pop();for(int i=head[x];i;i=ne[i]){int y=ver[i];if(d[y])continue;d[y]=d[x]+1;q.push(y);}}
}

广度优先遍历的两个重要性质：
1.在访问过所有第i层节点后，才会开始访问第i+1层节点。
2.任意时刻，队列中至多有两个层次的节点。若第一部分属于第i层，则第2部分属于i+1层，并且所有第i层节点排在第i+1层节点前面。也就是说，广度优先遍历队列中的元素关于层次满足“两段性”和“单调性”。

拓扑排序

拓扑排序的思想很简单，我们只需要不断选择图中入度为0的节点x，然后把x连向的点的入读减1.我们可以结合广度优先遍历的框架来高效地实现这个过程。
1.建立空的拓扑序列A。
2.预处理出所有的入度deg[i],起始把所有入度为0的点入队。
3.取出队头节点x，把x加到拓扑序A的末尾。
4.对于从x出发的每条边(x,y),把deg[y]减1.若被减数为0则把y入队。
5.重复3-4步直到队列为空，此时A即为所求。

void topsort()
{queue<int>q;for(int i=1;i<=n;i++)if(deg[i]==0)q.push(i);while(q.size()){int x=q.front();q.pop();a[++cnt]=x;for(int i=head[x];i;i=ne[i]){int y=ver[i];if(--deg[y]==0)q.push(y);}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}topsort();for(int i=1;i<=cnt;i++)printf("%d ",a[i]);cout<<endl;return 0;
}

例题
acwing164.可达性统计

先求出拓扑序，之后按照拓扑序的倒序依次求出每一个点所能到达的点的集合。

#include<iostream>
#include<bitset>
#include<queue>
using namespace std;
#define MAX_N 30000
int n,m;
int ver[MAX_N+5],ne[MAX_N+5],head[MAX_N+5];
int a[MAX_N+5];
int d[MAX_N+5];
int tot=0,cnt=0;
bitset<MAX_N+5>f[MAX_N+5];
void add(int x,int y)
{ver[++tot]=y,ne[tot]=head[x],head[x]=tot;return ;
}
void topsort()
{queue<int>q;for(int i=1;i<=n;i++)if(!d[i])q.push(i);while(q.size()){int x=q.front();q.pop();a[++cnt]=x;for(int i=head[x];i;i=ne[i]){int y=ver[i];if(--d[y]==0)q.push(y);}}return ;
}
int main()
{cin>>n>>m;for(int i=1,x,y;i<=m;i++){cin>>x>>y;add(x,y);d[y]+=1;}topsort();for(int i=n;i>=1;i--){int j=a[i];f[j][j]=1;for(int k=head[j];k;k=ne[k])f[j]|=f[ver[k]];}for(int i=1;i<=n;i++)printf("%d\n",f[i].count());return 0;
}