图（树的重心）

在上正题之前咱们就先浅浅的介绍一下：

树是一种特殊的图，一个无环连通图

图：有向图、无向图

有向图：a--->b

无向图a---b，既可以从a到b，也可以从b到a，所以无向图也可以称为是特殊的有向图

可以构建类似于有向图，a—>b,b—>a;

有向图的存储：

①邻接矩阵：不能存储重边，比较浪费空间，适合存稠密图

②邻接表：单链表：每一个结点都开一个单链表(存这个点可以走到哪)，比如：

 插入元素到单链表：

一般插入元素都是插到头节点的位置：时间复杂度O（1）

 插入代码：

#include
#include 
using namespace std;
const int N=110;
int h[N],e[N],ne[N],idx;//有n个结点有n个头结点
void add(int a,int b)//插入一个由a指向b的 
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
} 
int main(){
    memset(h,-1,sizeof(h));//初始化头节点为-1 
}

树和图的遍历：

深搜：

 宽搜：一层一层来搜：（数字代表层数）

 深搜和宽搜每个点就只能遍历一次

#include
#include 
using namespace std;
const int N=110;
int h[N],e[N],ne[N],idx;//有n个结点有n个头结点
bool st[N];//进行标记 
void add(int a,int b)//插入一个由a指向b的 
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
void dfs(int u)
{
    st[u]=true;//这个点已经被用过了
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];//当前链表里的结点对应图里面的点的编号
        if(!st[j]) dfs(j);//如果这个点没有遍历过，就一直往下搜，一条路走到黑
        //每个点就走过一次，所以用不着回溯（恢复现场） 
    } 
}
int main(){
    memset(h,-1,sizeof(h));//初始化头节点为-1 
}

下面用以上的板子来写题：

给定一颗树，树中包含 n">nn 个结点（编号 1∼n">1～n1～n）和 n−1">n?1n?1 条无向边。

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

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

输入格式

第一行包含整数 n">nn，表示树的结点数。

接下来 n−1">n?1n?1 行，每行包含两个整数 a">aa 和 b">bb，表示点 a">aa 和点 b">bb 之间存在一条边。

输出格式

输出一个整数 m">mm，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤105">1≤n≤1051≤n≤105

输入样例

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

输出样例：

4

这题看着让人头晕，但模拟一下样例，就可以知道要做什么了

 看这个样例，就知道要解决两个问题：

①如何求删去一个数，下面的连通块

②删去的这个点上面一圈连通块点的数量

令一个点为头节点（其实也就是删掉的那个点啦），用dfs进行深搜，就能知道下面的点数有多少

如何求上面：dfs只能往下不能往上，那把令的那个头节点删去，下面各个连通块的数量加起来，用总数来减就ok了

然后具体怎么实现呢：

就是枚举各个点的最大值，求他们中的最小的就好了

#include
#include 
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;//有n个结点有n个头结点
bool st[N];//进行标记 
int ans=N;//存的是最小的最大值 
int n;
void add(int a,int b)//插入一个由a指向b的 
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
int dfs(int u)//返回的是以u为根中子树的数量连通块的最大值 
{
    st[u]=true;//这个点已经被用过了
    int sum=1,res=0;//sum为当前这个子树的大小（本身算上所以初始值为1）， res为删掉那个点后每一个连通块中的最大值
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];//当前链表里的结点对应图里面的点的编号
        if(!st[j]) //如果这个点没有遍历过，就一直往下搜，一条路走到黑
        {
            int s=dfs(j);//当前连通块中的数量 
            res=max(res,s);//取最大值 
            sum+=s;//s只是一部分，需要求以u为根节点子树的数量，就是把局部的s加上去 
        }
        //每个点就走过一次，所以用不着回溯（恢复现场） 
    } 
    res=max(res,n-sum);//各个连通块中数量的最大值 
    ans=min(ans,res);//全部最大值的最小值 
    return sum;
}
int main(){
    memset(h,-1,sizeof(h));//初始化头节点为-1 
    cin>>n;
    for(int i=0;i1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<endl;
    return 0;
}