树和图的深度与广度优先遍历（树的重心，图中点的层次）

846. 树的重心

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一颗树，树中包含 n

个结点（编号 1∼n）和 n−1

条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n

，表示树的结点数。

接下来 n−1

行，每行包含两个整数 a 和 b，表示点 a 和点 b

之间存在一条边。

输出格式

输出一个整数 m

，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤105

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

/**
 * 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中
 * 点数的最大值最小，那么这个节点被称为树的重心。
 *
 * 由于是树，所以该图一定是连通的，那么求出每一个节点的最大子树的节点个数，
 * n个结点相比，得到最小的值就是答案。
 *
 * for(int i=0;i     {
        int v=Adj[u][i];
        if(hs[v]==0)
        {
            hs[v]=1;
            int j=dfs(v);
            sum+=j;  //累加子树的节点数
            ans=max(ans,j); //计算子树的最大节点数
            // hs[v]=0; //为什么这儿不需要回溯，是因为这是树，u的子节点
            //v1被访问了，那么u的子节点 v2 及v2 的子孙结点都不可能与v1
            //有边相连，否则就会出现回路；其实更准确的解释是树的每个节点
            //都只会被访问一次
        }
    }
*/

 
 
/**
 * 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中
 * 点数的最大值最小，那么这个节点被称为树的重心。
 * 
 * 由于是树，所以该图一定是连通的，那么求出每一个节点的最大子树的节点个数，
 * n个结点相比，得到最小的值就是答案。
 * 
 * for(int i=0;i
    {
        int v=Adj[u][i];
        if(hs[v]==0)
        {
            hs[v]=1;
            int j=dfs(v);
            sum+=j;  //累加子树的节点数
            ans=max(ans,j); //计算子树的最大节点数
            // hs[v]=0; //为什么这儿不需要回溯，是因为这是树，u的子节点 
            //v1被访问了，那么u的子节点 v2 及v2 的子孙结点都不可能与v1
            //有边相连，否则就会出现回路；其实更准确的解释是树的每个节点
            //都只会被访问一次
        }
    }
*/
 
/**
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int N = 1e5+10; // 最大边数
 
vector<int> Adj[N]; //邻接表
bool hs[N]; //顶点是否被访问
 
int res = N; //结果
int n; //顶点数
 
void Read() // 读入数据
{
    cin >> n;
    
    for(int i=1;i<n;++i)
    {
        int u,v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
}
 
int dfs(int u) //返回以u为根的所有子树的节点数(包括结点u)
{
    hs[u]=1;
    int sum=1,ans=0; //sum 记录以u为根的所有子树的的节点数，ans记录最大的子树的节点数
    
    for(int i=0;i<Adj[u].size();++i)
    {
        int v=Adj[u][i];
        if(hs[v]==0)
        {
            int j=dfs(v);
            sum+=j;  //累加子树的节点数
            ans=max(ans,j); //计算子树的最大节点数
        }
    }
    
    ans=max(ans,n-sum); //计算与u相连的连通块中最大的节点数
    res=min(res,ans);   //计算结果，各个节点的连通块中节点数中最大值中的最小值
    
    return sum;
}
 
int main()
{
    Read();
    
    dfs(1);
    
    cout << res << endl;
    
    return 0;
}
*/

847. 图中点的层次

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1

，点的编号为 1∼n

。

请你求出 1

号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1

。

输入格式

第一行包含两个整数 n

和 m

。

接下来 m

行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1

的边。

输出格式

输出一个整数，表示 1

号点到 n

号点的最短距离。

数据范围

1≤n,m≤105

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

这个题就和走迷宫所需步数的问法一摸一样：

 解法一：

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
const int maxn = 1e5+10;
vector<int> Adj[maxn];
int d[maxn];
int n,m;
 
void Read()
{
    cin >> n >> m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin >> u >> v;
        Adj[u].push_back(v);
    }
}
 
int bfs(int st)
{
    queue<int> q;
    q.push(st);
    d[st]=0;
    
    while(q.size())
    {
        int u=q.front();
        q.pop();
        if(u==n)
            return d[n];
            
        for(int i=0;i<Adj[u].size();++i)
        {
            int v=Adj[u][i];
            if(u!=v && d[v]==0) //必须判断u是否等于v，即判断是否为自环
            {
                q.push(v);
                d[v]=d[u]+1;
            }
        }
    }
    
    return -1;
}
 
int main()
{
    Read();
    
    cout << bfs(1) << endl;
    
    return 0;
}

解法二：堆优化的Dijkstra算法，将每一条边看成权值为1的有向边；

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
const int maxn = 1e5+10;
vector<int> Adj[maxn];
int d[maxn];
int n,m;
 
void Read()
{
    cin >> n >> m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin >> u >> v;
        Adj[u].push_back(v);
    }
}
 
int bfs(int st)
{
    queue<int> q;
    q.push(st);
    d[st]=0;
    
    while(q.size())
    {
        int u=q.front();
        q.pop();
        if(u==n)
            return d[n];
            
        for(int i=0;i<Adj[u].size();++i)
        {
            int v=Adj[u][i];
            if(u!=v && d[v]==0) //必须判断u是否等于v，即判断是否为自环
            {
                q.push(v);
                d[v]=d[u]+1;
            }
        }
    }
    
    return -1;
}
 
int main()
{
    Read();
    
    cout << bfs(1) << endl;
    
    return 0;
}