1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 定义全局变量,n为结点总数量,k为边的总数量 int n , k; // [2] 父节点数组,fa[i] 存储结点 i 的父节点编号 int fa[100100]; int main() { // [3] 读取输入的结点总数n和边的总数k cin >> n >> k; // [4] 初始化父节点数组:初始状态下每个结点的父节点为自身,即每个结点独立为一棵树 for(int i = 1 ; i <= n ; i++) fa[i] = i; // [5] 循环读取k条边的信息,构建结点间的父子关系 for(int i = 1 ; i <= k ; i++) { // [6] 读取边的两个端点,题目规定x是y的父节点 int x , y; cin >> x >> y; // [7] 设置结点y的父节点为x,将y合并到x所在的树中 fa[y] = x; } // [8] 统计树的总数量:根节点的判定条件为 父节点等于自身 int sum = 0; for(int i = 1 ; i <= n ; i++) { // [9] 若当前结点是根节点,树的总数加1 if(fa[i] == i) sum++; } // [10] 输出树的总数量 cout << sum << endl; // [11] 按从小到大的顺序,遍历输出每棵树的根节点编号 for(int i = 1 ; i <= n ; i++) { // [12] 若当前结点是根节点,输出其编号 if(fa[i] == i) cout << i << " "; } return 0; }
- 1
信息
- ID
- 1079
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者