1 条题解

  • 0
    @ 2026-2-17 17:45:09
    #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
    上传者