上算法基础课的笔记，题来源于下方，但是这篇不完全用于解题

AcWing 846. 树的重心 https://www.acwing.com/problem/content/848/

AcWing 847. 图中点的层次 https://www.acwing.com/problem/content/849/

1.邻接表

#include<iostream>
using namespace std;

int n;//总的结点数
const int N=1e5+10;
int h[N],e[N],ne[N];//e表示结点编号，h表示头结点下标，ne表示结点的下标
int idx;

//a表示头结点，b表示新插入的结点
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}

int main(){
    cin>>n;
    memeset(h,-1,size h);//初始化为-1

    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
}

2.深度搜索

bool st[N];//记录是否被遍历
void dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[u]){
        int j=e[i];
        if(!st[j]){
            dfs(j);
        }

    }
}

3.宽度搜索

dfs的模版：
第一个元素入队；
while(队列不为空){
    取出队头元素;
    队头元素出队;
    ……
    拓展队列;
    ……
}

queue<int> q;
int d[N];
void bfs(int u){
    memset(d,-1,sizeod d);
    q.push(u);//第一个元素入队
    d[u]=0;

    while(!q.empty()){
        auto t=q.front();//取出队头元素
        q.pop();//队头元素出队
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q.push(j);//拓展队列
            }
        }
    }

}