阅读量:0
思想：
代码：
#include <iostream> #include <cstring> using namespace std; const int N = 1e5 + 10; // vis标记当前节点是否被访问过; vis[1]=true代表编号为1的节点被访问过 bool vis[N]; // h数组为邻接表; h数组上的每个坑位都串了一个单链表; h[1]=3代表编号为1的节点的第一个邻接节点的编号为3 // e[i]代表编号为i的节点的值; ne[i]代表编号为i的节点的下一个节点的编号; idx代表当前可用编号; 注意这里的e和ne数组要开2*N的大小 int h[N], e[2 * N], ne[2 * N], idx; // res存储去掉各个节点后的最大连通块的最小值; 初始记录为最大值，最大值为最大连通块的点数，就是树中所有的节点数 int n, res = N; // 值为a的节点和值为b的节点之间存在一条边，在以a打头的单链表上插入头结点b void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } // 得到以u为根的树的总节点数 int dfs(int u) { vis[u] = true; // 标记u节点已经访问过 int size = 0; // 代表以u为根的最大子树的节点数; 初始时最大子树节点数为0 int sum = 1; // 代表以u为根的树的总节点数; 初始时该树的总节点数为1 // 遍历u节点的邻居; 也就是遍历u的每个儿子 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; // 得到u节点的邻居节点，也就是u的儿子 if (vis[j]) continue; //避免叶子结点找到的邻居节点为父节点 int s = dfs(j); // 得到以某个儿子节点为根的树的总节点数; 也就是某个子树的节点数 size = max(size, s); // 更新最大子树节点数 sum += s; // 累加所有子树的节点数 } // 如果删掉了u这个点，那么整个树可以分成两部分，u的所有子树和u的上面的剩余部分 // u的所有子树的最大节点数为size，剩余部分为整棵树的总节点数减去以u为根的树的节点数，求max后得到删去u后连通块中的最大节点数 // 再和删去其他节点的答案作比较，更新最小的最大连通块的点数 res = min(res, max(size, n - sum)); return sum; } int main() { cin >> n; // 首先要初始化邻接表h memset(h, -1, sizeof h); // 将输入的点构成邻接表 for (int i = 0; i < n - 1; i ++ ) { int a, b; cin >> a >> b; // 比如a=1 b=3，代表值为1的节点和值为3的节点之间存在边; 那么1的单链表后面要串个3，3的单链表后面要串个1 add(a, b); add(b, a); } // 从树中的任意一个节点开始dfs都可以; 比如也可以是dfs(n-1) dfs(1); cout << res << endl; return 0; } 