解题思路
利用树的深度遍历
对每个结点,算出删除它之后的各个连通块的最大结点数是多少
然后算出其中最小的
详细思路见代码注释
代码
#include#include #include using namespace std; const int N = 1e5 + 10; //数据范围是10的5次方 const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边 int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点 int e[M]; //存储元素 int ne[M]; //存储列表的next值 int idx; //单链表指针 int n; //题目所给的输入,n个节点 int ans = N; //表示重心的所有的子树中,最大的子树的结点数目 bool st[N]; //记录节点是否被访问过,访问过则标记为true //a所对应的单链表中插入b a作为根 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } //返回以u为根的子树中节点的个数,包括u节点,便于计算连通块的结点个数 int dfs(int u) { int res = 0; //存储 删掉某个节点之后,各连通子图中最大的连通子图节点数 st[u] = true; //标记访问过u节点 int sum = 1; //存储 以u为根的树 的节点数, 包括u,如图中的4号节点 //访问u的每个子节点 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过 if (!st[j]) { int s = dfs(j); // u节点的单棵以一个子节点为根的子树的节点数 如图中的size值 也即其作为把u删了以后的联通子块的结点数 res = max(res, s); // 记录以u的每个子节点为根的联通子块中最大联通子图的节点数 sum += s; //以j为根的树 的节点数 } } //n-sum 如图中的n-size值,不包括根节点4; res = max(res, n - sum); // 选择u节点为重心,最大的 连通子图节点数 其实是拿子节点的形成的最大的,与它上面的整体比 ans = min(res, ans); //遍历过的假设重心中,最小的最大联通子图的 节点数 return sum; } int main() { memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点 一定要记得,别忘了!!!这里是在初始化邻接表为没边 cin >> n; //表示树的结点数 // 题目接下来会输入,n-1行数据, // 树中是不存在环的,对于有n个节点的树,必定是n-1条边 for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); //无向图 } dfs(1); //可以任意选定一个节点开始 u<=n cout << ans << endl; return 0; } 作者:松鼠爱葡萄 链接:https://www.acwing.com/solution/content/13513/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)