时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个包含 N 个顶点 M 条边的无向图 G ，判断 G 是不是一棵树。
输入
第一个是一个整数 T ，代表测试数据的组数。 (1 ≤ T ≤ 10)
每组测试数据第一行包含两个整数 N 和 M 。(2 ≤ N ≤ 500, 1 ≤ M ≤ 100000)
以下 M 行每行包含两个整数 a 和 b ，表示顶点 a 和顶点 b 之间有一条边。(1 ≤ a, b ≤ N)
输出
对于每组数据，输出YES或者NO表示 G 是否是一棵树。
- 样例输入
-
2
3 2
3 1
3 2
5 5
3 1
3 2
4 5
1 2
4 1 - 样例输出
-
YES
NO 思路：判定是否为树的2个充要条件:①边的数目等于结点数-1 ②图连通(并查集只有一个根)#include <iostream>
#include <string.h>
using namespace std;
const int MAXN=;
int n,m;
int par[MAXN];
void prep()
{
for(int i=;i<MAXN;i++)
{
par[i]=i;
}
}
int fnd(int x)
{
if(x==par[x])
{
return x;
}
return par[x]=fnd(par[x]);
}
void unite(int x,int y)
{
int a=fnd(x);
int b=fnd(y);
par[a]=b;
}
int main()
{
int T;
cin>>T;
while(T--)
{
prep();
cin>>n>>m;
for(int i=;i<m;i++)
{
int x,y;
cin>>x>>y;
unite(x,y);
}
int root=-;
int cnt=;
for(int i=;i<=n;i++)
{
int fa=fnd(i);
if(fa!=root)
{
root=fa;
cnt++;
}
}
if(n-==m&&cnt==)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return ;
}