给定一个包含 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
分析：判断是否是一棵树，就是不能有环，还有所有的节点都是连通的
通过学习（电路分析）知道，一棵树必须有：节点数=边数+1
（哈哈，电路分析是开玩笑的，差一点就挂了）
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int m[505][505]; //记录数
int vis[505]; //记录节点
void bfs()
{
queue<int>q; //创建整型队列q
int h;
h=1;
vis[h]=1; //从节点1开始遍历
while(1)
{
for(int i=1;i<=500;i++)
{
if(m[h][i]==1&&vis[i]==0)
{
vis[i]=1;
q.push(i); //入队列
}
}
if(q.empty())
break;
h=q.front();
q.pop();
}
}
int main()
{
int T,a,b,M,N;
cin>>T;
while(T--)
{
int k;
memset(m,0,sizeof(m));
memset(vis,0,sizeof(vis));
cin>>N>>M;
k=M;
for(int i=0;i<M;i++)
{
cin>>a>>b;
if(m[a][b]!=0)
k--;
m[a][b]=1;
m[b][a]=1;
}
if(k!=N-1) //节点数=边数+1
cout<<"NO"<<endl;
else
{
int flag=1;
bfs();
for(int i=1;i<=M;i++)
{
if(vis[i]==0) //如果有节点没遍历到，表明数不是连通的
{
flag=0;
break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}
原文：http://www.cnblogs.com/xzxj/p/6580725.html