阿坝州网站建设公司

【判断一个图是否构成树（C++）】-创新互联

判断一个图是否构成树（C++） 问题描述

给定一个无向图，判断该图是否构成树。

梁河ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18980820575（备注：SSL证书合作）期待与您的合作！输入

输入有若干测试样例。第一行是测试样例个数，接下来若干测试样例。每个测试样例的第一行是结点数n，而且结点用1, 2, ..., n编号。第二行是边数m，接下来是m个结点对。

输出

如果一个图是树，则打印"YES"，否则打印"NO"。每个输出占一行。

输入样例
3

3
2
1 2
2 3

3
3
1 2
2 3
1 3

3
1
2 3
输出样例
YES
NO
NO
我的思路

思路：本题有n个顶点，如果构成树，就说明要有n-1条边，这是第一个判断条件；有了n-1条边，那就只有两种情况，一种是没有回路，构成一棵树，一种是有回路，有回路就说明图不连通，于是在输入结点对时就会有顶点从未出现，所以我用了set来存储结点对里出现的顶点序号，再循环查找，如果有顶点未出现，则不构成树。

代码
#include#include#include 
using namespace std;
int main()
{int num;
    cin >>num;
    while (num--)
    {int n, m, a, b;
        cin >>n >>m;
        unordered_setset;
        for (int i = 0; i< m; ++i)
        {cin >>a >>b;
            set.insert(a);
            set.insert(b);
        }
        if (n != m + 1)
        {cout<< "NO"<< endl;
        }
        else
        {int flag = 1;
            for (int i = 1; i<= n; ++i)
            {if (!set.count(i))
                {cout<< "NO"<< endl;
                    flag = 0;
                    break;
                }
            }
            if (flag == 1)
                cout<< "YES"<< endl;
        }
    }
}

第一次看到这道题的时候总觉得边和顶点间有点关系，很快写出来了，后来第二次再见到只觉得有点熟悉，就感觉有什么点没有抓到，在网上搜，看到的好多都是dfs，就不大想看，然后找到了之前自己写的代码，最后就想写一篇自己的blog，于是有了第一篇blog，嗯，当个学习记录吧。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前标题：【判断一个图是否构成树（C++）】-创新互联
转载注明：http://azwzsj.com/article/dojhsd.html

其他资讯