树的重心

给定一颗树，树中包含 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;
}