定义:
重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
不妨设max_part(x)为在删除节点x后产生的子树中,最大的一颗大小。那么树的重心就是使得max_part函数取到最小的节点p就是整颗树的重心。
void dfs(int x) { v[x] = 1; size[x] = 1; //设置子树的大小; int max_part = 0; //表示删除x后最大子树的大小; for (int i = head[x]; i; i = ne[i]) { int y= ver[i]; if (v[y]) continue; //点y已经被访问过了; dfs(y); size[x] += size[y]; //从子节点更新到父节点 max_part = max(max_part, size[y]); } max_part = max(max_part, n - size[x]); if (max_part < ans ) { ans = max_part; //全局量记录重心对应的max_part pos = x; //全局量pos记录重心; } }
本质上还是图着色,这里用cnt表示不同的颜色。
void dfs(int x) { v[x] = cnt; for (int i = head[x]; i; i = ne[i]) { int y = ver[i]; if (v[y]) continue; dfs(y); } } //依次着色森林; for (int i = 1; i <= n; i++) { if (!v[i]) { cnt++; dfs(i); } }