树与图的深度优先遍历

存储方式：

1. 邻接矩阵（一个二维数组）=> g[ a ] [ b ] = k; => a -->b 的权重为k。相反g[ b ] [ a ] = k; => b -->a 的权重为k。
2. 邻接表

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , M = 2 * N;
int h[N],e[M],ne[M],idx;
int n;
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int dfs(int u)
{
    for(int i = h[u] ; i != -1 ; i = ne[i])
    {
        int j = e[i];
        if(!b[j]) dfs(j);
    } 
}

例：acwing-846-树的重心

[题目链接](846. 树的重心 - AcWing题库)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , M = 2 * N;
int h[N],e[M],ne[M],idx;
int ans = N;
int n;
bool b[N];
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int dfs(int u)
{
    b[u] = true;
    int sum = 1 , cnt = 0;
    for(int i = h[u] ; i != -1 ; i = ne[i])
    {
        int j = e[i];
        if(b[j]) continue;
        
        int c = dfs(j);
        cnt = max(cnt,c);
        sum += c;
    }
    
    cnt = max(cnt,n-sum);
    ans = min(ans,cnt);
    
    return sum;
    
}

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