题目链接：http://hihocoder.com/problemset/problem/1322
时间限制: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
首先，如何判断一个图是不是一棵树。
第一个想到的当然是n-1条边；
那么光n-1条边就够了吗，显然还有一个条件，就是这个图是连通图。
它给的样例中，边不重复出现，那么判断m是否等于n-1其实非常方便；
所以我们只要想办法得到一个图是不是连通图即可。
从某种角度上来讲，可以说是一道裸的并查集模板题，那可以说就是一道水题了。
#include<cstdio>
using namespace std;
struct Edge{
int u,v;
};
int n,m;
int par[],ran[];
void init()
{
for(int i=;i<=n;i++) par[i]=i,ran[i]=;
}
int find(int x)
{
if(par[x] == x) return x;
else return( par[x] = find(par[x]) );
}
void unite(int x,int y)
{
x=find(x),y=find(y);
if(x == y) return;
if(ran[x] < ran[y]) par[x]=y;
else
{
par[y]=x;
if(ran[x] == ran[y]) ran[x]++;
}
}
bool isSame(int x,int y){return( find(x) == find(y) );}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
if(!isSame(from,to)) unite(from,to);
}
bool flag=;
int pa=find();
for(int i=;i<=n;i++)
{
if(pa!=find(i)){
flag=;
break;
}
}
if(flag && m==n-) printf("YES\n");
else printf("NO\n");
}
}
当然，如果不用并查集，用搜索的话，又可以是一道非常裸的DFS题？……embarrassing……
#include<cstdio>
#include<vector>
using namespace std;
struct Edge{
int u,v;
};
vector<Edge> adj[];
int n,m;
bool vis[];
void dfs(int now)
{
vis[now]=;
for(int i=;i<adj[now].size();i++)
{
Edge edge=adj[now][i];
int next=edge.v;
if(!vis[next]) dfs(next);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
adj[i].clear();
vis[i]=;
}
for(int i=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
adj[from].push_back((Edge){from,to});
adj[to].push_back((Edge){to,from});
}
dfs();
bool flag=;
for(int i=;i<=n;i++)
{
if(!vis[i]){
flag=;
break;
}
}
if(flag && m==n-) printf("YES\n");
else printf("NO\n");
}
}
然后又随手码了一个BFS模板……在新加坡就是这么刷水题的……感觉对不起自己现在熬的夜……难受……
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct Edge{
int u,v;
};
vector<Edge> adj[];
int n,m;
bool vis[];
void bfs()
{
queue<int> q;
q.push();
vis[]=;
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=;i<adj[now].size();i++)
{
Edge edge=adj[now][i];
int next=edge.v;
if(!vis[next]){
vis[next]=;
q.push(next);
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
adj[i].clear();
vis[i]=;
}
for(int i=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
adj[from].push_back((Edge){from,to});
adj[to].push_back((Edge){to,from});
}
bfs();
bool flag=;
for(int i=;i<=n;i++)
{
if(!vis[i]){
flag=;
break;
}
}
if(flag && m==n-) printf("YES\n");
else printf("NO\n");
}
}