【判断一个图是否构成树(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++)】-创新互联
URL地址:http://pwwzsj.com/article/dojhsd.html