DFS

#include<iostream>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int N=110;
int h[N],e[N],ne[N];
int st[N];
int idx;
int n,m;
map<int,int>ans;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int r=0;
void bfs(){
    queue<int>res;
    res.push(1);
    st[1]=1;

    while(!res.empty()){
        int s=res.size();
       for(int j=0;j<s;j++){
        int temp=res.front();
        res.pop();
        if(h[temp]==-1){
            ans[r]++;

        }
        else{
        for(int i=h[temp];i!=-1;i=ne[i]){
            if(st[e[i]]==0){
                res.push(e[i]);
                st[e[i]]=1;
            }
        }
        }
    }
     r++;
    }

}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int id,k,x;
        cin>>id>>k;
        for(int j=0;j<k;j++){
            cin>>x;
            add(id,x);
        }
    }
    bfs();

    for(int i=0;i<r;i++){

        if(!ans.count(i)){
            cout<<0<<' ';
        }
        else
        cout<<ans[i]<<' ';
    }
    return 0;
}

DFS

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int h[N],e[N],ne[N];
int idx;
int cnt[N];
void init(int a,int b)
{

    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int max_depth=0;
int d;
void bfs(){
    queue<int>tree;
    tree.push(1);
    while(!tree.empty()){

        int si=tree.size();

        for(int i=0;i<si;i++){
            int f=tree.front();
            tree.pop();
            if(h[f]==-1){
                cnt[d]++;
            }else{
                for(int j=h[f];j!=-1;j=ne[j]){
                    tree.push(e[j]);
                }
            }

        }
        d++;
    }
    for(int i=0;i<d;i++){
        cout<<cnt[i]<<' ';
    }
}
int main(){
    int m,n;
    cin>>m>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++){
        int root,s;
        scanf("%d%d",&root,&s);
        while(s--){
            int x;
            scanf("%d",&x);
            init(root,x);
        }

    }
  bfs();
  return 0;
}

1497. 树的遍历

//特别注意：树节点值不一定是1~N
#include<bits/stdc++.h>
using namespace std;
const int N=40;
int post[N];
unordered_map<int,int>l,r,order;

int build(int il,int ir,int pl,int pr){
    int root=post[pr];
    int qu=order[root];
    if(il<qu){
        l[root]=build(il,qu-1,pl,pl+(qu-1-il));
    }
    if(qu<ir){
        r[root]=build(qu+1,ir,pr+(-ir+qu),pr-1);
    }
    return root;
}
vector<int>res;
void bfs(int rr){
    queue<int>ans;
    ans.push(rr);
    res.push_back(rr);
    while(!ans.empty()){
        int f=ans.front();
        ans.pop();
       /* for(int i=h[f];i!=-1;i=ne[i]){
            int temp=e[i];
            ans.push(temp);
            res.push_back(temp);
        }*/

        if(l.count(f)){
            ans.push(l[f]);
            res.push_back(l[f]);
        }
         if(r.count(f)){
            ans.push(r[f]);
            res.push_back(r[f]);
        }
    }
    for(auto &tt:res){
        cout<<tt<<' ';
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        post[i]=x;
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        order[x]=i;//保存每一个中序遍历数所在的位置
    }
    int root=build(0,n-1,0,n-1);//题目中并没有说明根节点的下标
    bfs(root);
    return 0;
}

1498. 最深的根

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int p[N];
int st[N];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

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

int ma;
void dfs(int u, int depth)
{
   st[u]=1;//必不可少！！！
    if(h[u]==-1)
    {
       return ;

    }
     ma=max(ma,depth);//这里注意：这里的树是无向图，所以深度需要实时更新！！！
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(st[j]==-1){

            dfs(j,depth+1);
        }


    }

}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int k = n;
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b))
        {
            k -- ;
            p[find(a)] = find(b);
        }
        add(a, b), add(b, a);
    }

    if (k > 1) printf("Error: %d components", k);
    else
    {

    unordered_map<int,vector<int>>nodes;
    int ans=0;
        for (int i = 1; i <= n; i ++ )
        {
            memset(st,-1,sizeof st);
            ma=0;
             dfs(i, 0);
          ans=max(ans,ma);

           nodes[ma].push_back(i);
        }

        for(auto &t:nodes[ans]){
            cout<<t<<endl;
        }
    }

    return 0;
}