一：树的重心（DFS）

• 邻接表用vector存储的效率不如使用数组存储效率高。
• 输入的数据超过100万的时候需要考虑使用scanf
• 树的BFS和DFS因为每一个点都是只遍历一次，所以时间复杂度是O(M+ N)

下面的写的博客非常好
https://www.acwing.com/solution/content/13513/
代码剩下的注释不写了，直接看上面的人的就很好

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N; // 无向图，用有向图模拟，树是无环的无向连通图，边的数目是2n - 2
int h[N], e[M], ne[M], idx; // h代表邻接表的n个顶点 e数组存储的是相邻的点是什么，下标用idx去表示，idx的作用就是邻接表数据结构
int ans = N; // ans最终的答案。
int n;
bool st[N]; // 标记每个点有没有被访问
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; // 链表的标准操作，这里建立邻接表只需要多一个下标参数
}
int dfs(int u)
{
    int sum = 1;  
    int res = 0;
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j);
            sum += s;
            res = max(res, s);
        }
    }
    res = max(res, n - sum); // 这里也没有什么问题，详细考虑过
    ans = min(ans, res);
    return sum;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

• 二刷问题很多，关键就是思路不清晰，每一轮的递归最起码应该知道求解的是什么，这个题二刷，甚至搞错返回值是什么
• 逻辑，点需要记录有没有访问，已经访问在哪里写都搞错
• 无向图
• 还有就是最小值，初始值设置最大
• 这个题无向图的好处就是，遍历的起点无所谓，从哪个起点开始，因为是无向图，都可以看作根节点。如果你不用无向图，很有可起始dfs(1)不对，因为可能不是根节点了，你用了无向图，就一定是双边，因为用的邻接表写的，两个点一定相互连接，所以一定要有状态，表示某个点已经访问，避免再次访问。

  二：图中点的层次

  广搜很轻松就能解决，图的添加，广搜的公式。
  ```cpp

  include

  include

  include

using namespace std;

const int N = 1e5 + 10, M = 2 * N; int h[N], e[M], ne[M], idx; int n, m; int d[N], q[N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }

int bfs() { q[0] = 1; memset(d, -1, sizeof d); d[1] = 0; int hh = 0, rr = 0; while (hh <= rr) { int u = q[hh++]; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[u] + 1; q[++rr] = j; } } } return d[n]; }

int main() { memset(h, -1, sizeof d); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; add(a, b); } cout << bfs() << endl; return 0; }

<a name="dj2j3"></a>
## 三：拓扑序列
有向无环图一定存在拓扑序列
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int n, m;
int d[N], q[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int topsort()
{
    int hh = 0, rr = -1;
    for (int i = 1; i <= n; i++) //找到所有的入读为0的点，题目条件是从1-n，所以这里遍历的时候，从1开始
    {
        if (d[i] == 0)
        {
            q[++rr] = i;
        }
    }
    while (hh <= rr)
    {
        int u = q[hh++];
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--; // 因为出队列的时候， 相当于一条边被删除了，自然指向的点的入度减一
            if (d[j] == 0)
            {
                q[++rr] = j;
            }
        }
    }
    return rr;
}
int main()
{
    memset(h, -1, sizeof h); // 构建图不用多说
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] += 1;
    }
    if (topsort() == n - 1) // 形成拓扑序列的时候，队列中存储了0-n-1的所有元素
    {
        for (int i = 0; i < n; i++)
        {
            cout << q[i] << " ";
        }
        cout << endl;
    } else {
        cout << "-1" << endl;
    }
    return 0;
}