hihocoder 1322

题目链接：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 是否是一棵树。

样例输入

样例输出

YES
NO

首先，如何判断一个图是不是一棵树。

第一个想到的当然是n-1条边；

那么光n-1条边就够了吗，显然还有一个条件，就是这个图是连通图。

它给的样例中，边不重复出现，那么判断m是否等于n-1其实非常方便；

所以我们只要想办法得到一个图是不是连通图即可。

从某种角度上来讲，可以说是一道裸的并查集模板题，那可以说就是一道水题了。

 1 #include<cstdio>
 2 using namespace std;
 3 struct Edge{
 4     int u,v;
 5 };
 6 int n,m;
 7 int par[505],ran[505];
 8 void init()
 9 {
10     for(int i=1;i<=n;i++) par[i]=i,ran[i]=0;
11 }
12 int find(int x)
13 {
14     if(par[x] == x) return x;
15     else return( par[x] = find(par[x]) );
16 }
17 void unite(int x,int y)
18 {
19     x=find(x),y=find(y);
20     if(x == y) return;
21     if(ran[x] < ran[y]) par[x]=y;
22     else
23     {
24         par[y]=x;
25         if(ran[x] == ran[y]) ran[x]++;
26     }
27 }
28 bool isSame(int x,int y){return( find(x) == find(y) );}
29 int main()
30 {
31     int t;
32     scanf("%d",&t);
33     while(t--)
34     {
35         scanf("%d%d",&n,&m);
36         init();
37         for(int i=1;i<=m;i++)
38         {
39             int from,to;
40             scanf("%d%d",&from,&to);
41             if(!isSame(from,to)) unite(from,to);
42         }
43         bool flag=1;
44         int pa=find(1);
45         for(int i=2;i<=n;i++)
46         {
47             if(pa!=find(i)){
48                 flag=0;
49                 break;
50             }
51         }
52         if(flag && m==n-1) printf("YES
");
53         else printf("NO
");
54     }
55 }

当然，如果不用并查集，用搜索的话，又可以是一道非常裸的DFS题？……embarrassing……

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 struct Edge{
 5     int u,v;
 6 };
 7 vector<Edge> adj[505]; 
 8 int n,m;
 9 bool vis[505];
10 void dfs(int now)
11 {
12     vis[now]=1;
13     for(int i=0;i<adj[now].size();i++)
14     {
15         Edge edge=adj[now][i];
16         int next=edge.v;
17         if(!vis[next]) dfs(next);
18     }
19 }
20 int main()
21 {
22     int t;
23     scanf("%d",&t);
24     while(t--)
25     {
26         scanf("%d%d",&n,&m);
27         for(int i=1;i<=n;i++)
28         {
29             adj[i].clear();
30             vis[i]=0;
31         }
32         for(int i=1;i<=m;i++)
33         {
34             int from,to;
35             scanf("%d%d",&from,&to);
36             adj[from].push_back((Edge){from,to});
37             adj[to].push_back((Edge){to,from});
38         }
39         dfs(1);
40         bool flag=1;
41         for(int i=1;i<=n;i++)
42         {
43             if(!vis[i]){
44                 flag=0;
45                 break;
46             }
47         }
48         if(flag && m==n-1) printf("YES
");
49         else printf("NO
");
50     }
51 }

然后又随手码了一个BFS模板……在新加坡就是这么刷水题的……感觉对不起自己现在熬的夜……难受……

 1 #include<cstdio>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 struct Edge{
 6     int u,v;
 7 };
 8 vector<Edge> adj[505];
 9 int n,m;
10 bool vis[505];
11 void bfs()
12 {
13     queue<int> q;
14     q.push(1);
15     vis[1]=1;
16     while(!q.empty())
17     {
18         int now=q.front();q.pop();
19         for(int i=0;i<adj[now].size();i++)
20         {
21             Edge edge=adj[now][i];
22             int next=edge.v;
23             if(!vis[next]){
24                 vis[next]=1;
25                 q.push(next);
26             }
27         }
28     }
29 }
30 int main()
31 {
32     int t;
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d%d",&n,&m);
37         for(int i=1;i<=n;i++)
38         {
39             adj[i].clear();
40             vis[i]=0;
41         }
42         for(int i=1;i<=m;i++)
43         {
44             int from,to;
45             scanf("%d%d",&from,&to);
46             adj[from].push_back((Edge){from,to});
47             adj[to].push_back((Edge){to,from});
48         }
49         bfs();
50         bool flag=1;
51         for(int i=1;i<=n;i++)
52         {
53             if(!vis[i]){
54                 flag=0;
55                 break;
56             }
57         }
58         if(flag && m==n-1) printf("YES
");
59         else printf("NO
");
60     }
61 }