树的重心
给定一颗树，树中包含?nn?个结点（编号?1～n1～n）和?n?1n?1?条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数?nn，表示树的结点数。
接下来?n?1n?1?行，每行包含两个整数?aa?和?bb，表示点?aa?和点?bb?之间存在一条边。
输出格式
输出一个整数?mm，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤1051≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：?
4该题是无向图，稀疏图，我们采用临接表的形式来进行存储， 类似于单链表的存储方式。
首先对h 处理成-1。
然后是add操作，也就是对两个点进行连边，由于我们是无向图，也就是说我们需要两边各连一次，重复两次add操作。
int dfs(int u)
{
? ? st[u] = true;
? ? for (int i = h[u]; i != -1; i = ne[i])
? ? {
? ? ? ? int j = e[i];
? ? ? ? if (st[j]) continue; //访问过就跳过
????????dfs(j);?
? ? }
}
然后具体到这道题目就是不同的dfs，返回的数据类型等。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N],e[M],ne[M],idx;
int ans=N;
bool vis[N];
void add(int a,int b){ //建图，链式前向星
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int dfs(int u){
vis[u]=1; //标记走过
int size=0,sum=0; //前者为存删除u点后，最大的连通子图节点数，后者为以u为根的节点数（用来求该点上面连通块的点数的）
for(int i=h[u];i!=-1;i=ne[i]){ //深搜
int j=e[i];
if(vis[j]) continue; //如果走过，那就不用管
int s=dfs(j); //s为u点下面以j为结点的连通块的点数
size=max(size,s); // 这是在求u点之下连通块的点数，来找一个最大值
sum+=s;
}
size=max(size,n-sum-1); //与u点上面连通块的点数，取个最大值
ans=min(ans,size); //这是求答案，根据题目，求删掉各个点后，最小的最大连通块点数
return sum+1;
}
int main(){
scanf("%d",&n);
memset(h,-1,sizeof(h));
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs(1);
printf("%d\n",ans);
return 0;
}
//Wraith_G这里引用一下?Wraith_G 的代码，很感谢！因为我的注释写的不清楚。。
对于bfs：
图中点的层次：
给定一个?nn?个点?mm?条边的有向图，图中可能存在重边和自环。
所有边的长度都是?11，点的编号为?1～n1～n。
请你求出?11?号点到?nn?号点的最短距离，如果从?11?号点无法走到?nn?号点，输出??1?1。
输入格式
第一行包含两个整数?nn?和?mm。
接下来?mm?行，每行包含两个整数?aa?和?bb，表示存在一条从?aa?走到?bb?的长度为?11?的边。
输出格式
输出一个整数，表示?11?号点到?nn?号点的最短距离。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1这道题目，像是低配版的dijkstra，由于边的长度为1， 并且存在重边和自环，输出的是1到n的距离，更形象的说n是1节点的第几层根。
?然后就可以写了，用bfs，不断地插入，取出数据，然后用图的遍历来进行判断，符合要求的押入队列。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e05 + 10, M = N * 2;
int read(){
int res = 0 , flag = 1 ;
char c = getchar() ;
while(!isdigit(c)){
if(c == '-') flag = -1 ;
c = getchar() ;
}
while(isdigit(c)){
res = (res << 1) + (res << 3) + (c ^ 48) ;
c = getchar() ;
}
return res * flag ;
}
int e[N], ne[N], h[N], idx;
int d[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int n, m;
int bfs() {
queue<int> q;
q.push(1);
memset(d, -1, sizeof d);
d[1] = 0;
while (q.size()) {
auto u = q.front();
q.pop();
for (int i = h[u]; i != -1; i = ne[i]) {
int t = e[i];
if (d[t] == -1) { //没有被访问过
d[t] = d[u] + 1; //
q.push(t);
}
}
}
return d[n];
}
int main() {
memset(h, -1, sizeof h);
n = read();
m = read();
for (int i = 0; i < m; i++) {
int a, b;
a = read();
b = read();
add(a, b);
}
cout << bfs();
return 0;
}