一、树的重心
对于一棵树来说，通常信息都是自顶向下传递的，比如树的深度；但也有自底向上传递的信息，比如以节点x为根的子树的大小 size [x] .size [叶子节点]=1；若节点 x 有k个子节点y1yk,并且以y1yk为根的子树大小分别是，size [y1], size [y2]……size [yk],则以x为根的子树的大小就是
size [x] = size [y1] + size [y2]+……size [yk]+1.
对于节点 x，如果把它从树中删除，那么原来的树可能被分成若干个不相连的部分，其中每一部分都一棵子树，设 max_part (x)表示删除节点x之后产生的子树中 最大的一棵的大小；使max_part ( )取到最小值的节点 p为整棵树的重心。
void dfs(int x){
v[x]=1;
size[x]=1;//子树的大小
int max_part=0;//删除 x后分成的最大子树的大小
for(int i=head[x];i;i=next[i]){ //head[]为树的邻接表的表头
//next[] 模拟链表指针
int y=ver[i];//ver[]存储边的终点
if(v[y]) continue;//点y已经访问过
dfs(y);
size[x]+=size[y];//从子节点向父节点递推
max_part=max(max_part,size[y]);
}
max_part=max(max_part,size[x]);//n为整棵树的节点数目
if(max_part<ans){
ans=max_part;//全局变量ans--树的重心对应的 max_part
pos=x;//全局变量pos--树的重心
}
}
二、图的联通块
//此时 v[]数组标记每个点属于哪一个联通块
void dfs(int x){
v[x]=cnt;
for(int i=head[x];i;i=next[i]){
int y=ver[i];
if(v[y]) continue;
dfs(y);
}
}
//在int main()中
for(int i=1;i<=n;i++){
if(!v[i]){
cnt++;//表示无向图包含的联通块的个数
dfs(i);
}
}
三、拓扑排序
拓扑排序是对图结点关系进行的排序，其排序结果提供了一种无后效性的遍历图的方式，即：后续结点不会影响之前的结点。此性质可用于动态规划、关键路径等。
只有有向无环图才有拓扑序列。
排序过程：将入度为零的结点放入一种存储结构（栈或队列）中，每次从存储结构中取出一个结点，将其能够直达的所有结点入度减一，若此时入度为零将则其加入存储结构，如此反复直至存储结构为空。
拓扑排序可以判定有向图中是否存在环，求出拓扑序列A之后，若A序列的长度小于图中点的数量，则说明某些节点没有被遍历，即图中存在环。
void add(int x,int y){//在邻接表中添加一条有向边
ver[++tot]=y,next[tot]=head[x],head[x]=tot;
deg[y]++;
}
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=next[i]){
int y=ver[i];
if(--deg[y]==0) q.push(y);
}
}
}
int main(){
cin>>n>>m;//n点数,m边数
for(int i=1;i=m;i++){
int x,y;
cin>>x>>y;
add(x,y);
}
topsort();
for(int i=1;i<=cnt;i++) cout<<a[i]<<' ';
}
《算法进阶指南》例题：可达性统计（拓扑排序+bitset二进制数组）
题目链接: 164. 可达性统计
/*题解：设点x出发能到达的点构成的结合为f[x],
先使用拓扑排序求出x的后继节点，然后按照拓扑排序的逆序进行计算
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt, ver[30005],net[30005],head[30005],tot,deg[30005],a[30005];
//cnt代表拓扑排序中点的个数
bitset<30005> f[30005];//二进制数组存储答案
void add(int x,int y){//在邻接表中添加一条有向边
ver[++tot]=y;net[tot]=head[x];head[x]=tot;
deg[y]++;//表示入度
}
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=net[i]){
int y=ver[i];
if(--deg[y]==0) q.push(y);
}
}
}
int main(){
cin>>n>>m;//n点数,m边数
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
add(x,y);
}
topsort();
//逆序
for(int j=cnt;j;j--){
int x=a[j];
f[x][x]=1;
for(int i=head[x];i;i=net[i]){
int y=ver[i];
f[x] |=f[y];//求出集合
}
}
for(int i=1;i<=cnt;i++) cout<<f[i].count()<<endl;//查 1的个数
}