一、树的深度：
  树中各个节点的深度是一种自顶向下的统计信息。起初，我们已知根节点的深度为0。若节点x的深度为d（x），则它的子节点y的深度就是d（y）=d（x）+1。在深度优先遍历的过程中结合自顶向下的递推，就可以求出每个节点的深度d。

void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=nt[x])
    {
        int y=ver[i];
        if(v[y]) continue;
        d[y]=d[x]+1;
        dfs(y);
    }
}

二、树的重心：
  也有许多信息是自底向上进行统计的，比如以每个节点x为根的子树大小size（x）。对于叶子节点，我们已知以它为根的子树大小为1。若节点x有k个子节点y1，y2……yk。并且以他们为根的子树大小分别是size（y1），size（y2），……size（yk），则以x为根的子树的大小就是size（x）=size（y1）+ size（y2）+ ……+ size（yk）+ 1.
  
  对于一个节点x，如果我们把它从树中删除，那么原来的一棵树可能会分成若干个不相连的部分，其中每一部分都是一棵子树。设max_part（x）表示在删除节点x后产生的子树中，最大的一棵大小。使max_part函数取到最小值的节点p就称为整棵树的重心。
  通过下面的代码，我们可以统计出size数组，并求出树的重心。

void dfs(int x)
{
    v[x]=1;
    _size[x]=1;
    int max_part=0;
    for(int i=head[x];i;i=nt[x])
    {
        int y=ver[i];
        if(v[y]) continue;
        dfs(y);
        _size[x]+=_size[y];
        max_part=max(max_part,_size[y]);
    }
    max_part=max(max_part,n-_size[x]);
    if(max_part<ans)
    {
        ans=max_part;
        pos=x;
    }
}

三、连通块划分：
  也可以用并查集。
  上面的代码从x开始一次遍历，就会访问x能够到达的所有的点与边。因此，通过多次深度优先遍历，可以划分出一张无向图中的各个连通块。同理，对一个森林进行深度优先遍历，可以划分出森林中的每棵树。如下面的代码所示，cnt就是无向图包含的连通块的个数，v数组标记了每个点属于哪一个连通块。

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

四、拓扑排序：
  有向无环图：在有向图中，从一个节点出发，最终回到它自身的路径被称为环。不存在环的有向图即为有向无环图。
  在有向图中，以节点x为终点的有向边的条数被称为x的入度，以节点x为起点的有向边的条数称为x的出度。
  在无向图中，以x为端点的无向边的条数被称为x的度。

  给定一张有向无环图，若一个由图中所有点构成的序列A满足：对于图中的每条边（x，y），x在A中都出现在y之前，则称A是该有向无环图顶点的一个拓扑序。求解A序列的过程称为拓扑排序。
  拓扑排序过程的思想非常简单，我们只需要不断选择图中入度为0的节点x，然后把x连向的点的入度-1。我们可以结合广度优先遍历的框架来高效的实现这个过程。
  建立空的拓扑序列A
  预处理出所有点的入度deg（i），起初把所有入度为0的点入队
  取出队头节点x，把x加入拓扑序列A的末尾
  对于从x出发的每条边（x，y），把deg（y）-1.若被减为0，则把y入队。
  重复以上两步直到队列为空，此时A即所求。

  拓扑排序可以判定有向图中是否有环。我们可以对任意有向图执行上述过程，完成后检查A序列的长度。若A序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。

void add(int x,int y)
{
    ver[++tot]=y;
    nt[tot]=head[x];
    head[x]=tot;
    deg[y]++;
}
void topsort(void)
{
    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=nt[i])
        {
            int y=ver[i];
            if(--deg[y]==0) q.push(y);
        }
    }
}

int main(void)
{
    cin>>n>>m;
    for(itn i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y);
    }
    topsort();
    for(int i=1;i<=cnt;i++)
        printf("%d ",a[i]);

    return 0;
}

例题：
Labeling Balls POJ - 3687：
这题得反向拓扑，还得判断重边。
反向的话可以保证比一个数大的可以在这个数后的都在这个数后。
正向的话无法保证比一个数大的可以在这个数后面的都在这个数后面。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=50050;
int head[maxn],ver[maxn],nt[maxn],d[maxn];
int st[maxn];
int la[maxn];
int tot,cnt;
bool ha[210][210];
void init(void)
{
    memset(head,0,sizeof(head));
    memset(d,0,sizeof(d));
    memset(ha,0,sizeof(ha));
    tot=cnt=0;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
    d[y]++;
}

void topsort(int n)
{
    priority_queue<int>q;
    for(int i=1;i<=n;i++)
        if(d[i]==0) q.push(i);
    while(q.size())
    {
        int x=q.top();q.pop();
        st[++cnt]=x;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(--d[y]==0) q.push(y);
        }
    }
    return ;
}

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        int n,m,x,y;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);

            if(!ha[x][y])
            add(y,x),ha[x][y]=true;
        }
        topsort(n);
        if(cnt!=n)
            printf("-1\n");
        else
        {
            for(int i=1;i<=n;i++)
                la[st[i]]=n-i+1;
            for(int i=1;i<=n;i++)
            {
                if(i!=1) putchar(' ');
                printf("%d",la[i]);
            }
            putchar('\n');
        }
    }
    return 0;
}

五、直径：
  树的直径
  给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路

径边权之和。树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最

长链。后者通常也可称为直径，即直径是一个 数值概念，也可代指一条路径

  树的直径通常有两种求法，时间复杂度均为O(n)。我们假设树以N个点N-1条边的无向图形式给

出，并存储在邻接表中。

  树形DP求树的直径
  设1号节点为根,"N个点N-1条边的无向图"就可以看做“有根树”

  设d[x]表示从节点x出发走向以x为根的子树，能够到达的最远节点的距离。设x的子

节点为y1,y2, y3, …, yt，edge(x, y)表示边权，显然有"d[x] = max{d[yi] + edge(x, yi)}(1 <= i <= t)

接下来，我们可以考虑对每个节点x求出"经过节点x的最长链的长度"f[x]，整棵树的直径就是max{f[x]}(1 <= x <= n)

  对于x的任意两个节点yi和yj，"经过节点x的最长链长度"可以通过四个部分构成：从yi到yi子树中的最远距离，边(x, yi)，边(x, yj)，从yj到yj子树中的最远距离。

设j < i，因此：f[x] = max{d[yi] + d[yj] + edge(x, yi) + edge(x, yj)}(1 <= j < i <= t)

但是我们没有必要使用两层循环来枚举i, j。在计算d[x]的过程，子节点的循环将要枚举到 i 时d[x]恰好就保存了从节点x出发走向“以yj(j < i)为根的子树”，能够到达的最远节点的距离，这个距离就是max{d[yj] +edge(x, yj)}(1 <= j < i)。所以我们先用d[x] + d[yi] + edge(x, yi)更新f[x]，再用d[yi] + edge(x, yi)更新d[x]即可。

void dp(int x)
{
    v[x]=1;
    for(int i=head[x];i;i=nt[x])
    {
        int y=ver[i];
        if(v[y]) continue;
        dp(y);
        ans=max(ans,d[x]+d[y]+edge[i]);
        d[x]=max(d[x],d[y]+edge[i]);
    }
}

  两次BFS（DFS）求树的直径
  通过两次BFS或者两次DFS也可以求树的直径，并且更容易计算出直径上的具体节点
详细地说，这个做法包含两步：
1.从任意节点出发，通过BFS和DFS对树进行一次遍历，求出与出发点距离最远的节点记为p

2.从节点p出发，通过BFS或DFS再进行一次遍历，求出与p距离最远的节点，记为q。

从p到q的路径就是树的一条直径。因为p一定是直径的一端，否则总能找到一条更长的链，与直径的定义矛盾。显然地脑洞一下即可。p为直径的一端，那么自然的，与p最远的q就是直径的另一端。
在第2步的遍历中，可以记录下来每个点第一次被访问的前驱节点。最后从q递归到p，即可得到直径的具体方案。
只给出遍历代码，从任意一点开始遍历，找到最大值。从最大值再进行一次遍历，找到最大值，即为直径。

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=nt[x])
    {
        int y=ver[i];
        if(vis[y]) continue;
        dis[y]=dis[x]+edge[i];
        dfs(y);
    }
}