树的深度优先遍历与广度优先遍历

1、数的深度优先遍历
https://www.acwing.com/problem/content/848/

重心—就是树的结点，需符合删掉这个结点后 形成的连通块中结点数最多的连通块 与 删去其他某一结点后 形成的连通块中结点数最多的连通块 相比 结点数最少

考虑点：如何进行删除结点—然后计算删除后连通块结点数—最后进行比较

采用dfs遍历，记录每个根结点所能连通结点的个数 ，在dfs过程中计算此结点的各个孩子结点连通的结点个数，及除去此结点连通结点的个数剩余的个数，进行比较
求值

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n;
bool vis[N];
//邻接表构建--模板
int e[N],ne[N],h[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int ans;

int dfs(int u){
    //size 记录此结点的各个孩子结点连通块中结点数最多的数目
    //sum 把这些加起来
    int size=0,sum =0;
    for(int i=h[u];i!=-1;i=ne[i]){
        //没有遍历过
        if(vis[e[i]]) continue;
        vis[e[i]]=true;
        
        //返回此孩子结点连通块结点的个数
        int s = dfs(e[i]);
        
        sum+=s;
        
        size = max(size,s);
    }
    //除去此结点连通结点的个数
    //与size比较
    size = max(size,n-sum-1);
    
    ans = min(ans,size);
    
    //包含本身
    return sum+1;
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        //无向图---相当于特色的有向图
        //1->2  2->1
        add(a,b);
        add(b,a);
    }
    ans = N;
    //起始结点1放入--已经遍历过
    vis[1]=true;
    dfs(1);
    cout<<ans;
    return 0;
}

2、数的广度优先遍历
https://www.acwing.com/problem/content/description/849/
一层一层外搜
记录每个点到n的距离

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2*N;

int n,m;
bool vis[N];
int d[N];
//邻接表构建
int e[N],ne[N],idx,h[N];

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int bfs(){
    queue<int> q;
    q.push(1);
    vis[1]=true;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        
        int step = d[t];
        
        if(t == n) return step;
        
        for(int i=h[t];i!=-1;i=ne[i]){
            
            int j =e[i];
            
            if(vis[j]) continue;
            vis [j] = true;
            
            d[j] = step+1;
            
            q.push(j);
            
        }
    }
    return -1;
}
int main(){
    memset(h,-1,sizeof(h));
    d[n]=-1;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs();
    return 0;
}