并查集的应用

题意：

　　　　　　　　A | B R

　　　　　　 | | | |

B | E C

/ 　　　　　　　　　　　　　　　　　　　　| / | |

　　　　　　C D | H I J P

这是一棵树这是一片森林

Input：

输入两个数n和m ，n表示多少个点，m表示有多少的无向边（题目保证无重边，无自环（即a走到a））

Output:

如果是树输出：This is a tree

如果是森林：This is a forest

如果什么不是：This is a graph

代码：

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 #define N 100005
 7 int f[N];
 8 
 9 int find(int x)
10 {
11     return x == f[x] ? x : f[x] = find(f[x]);
12 }
13 int main()
14 {
15     int n, m, i, xx, yy, x, y, mark, fNum;
16     while(scanf("%d%d", &n, &m)!=EOF)
17     {
18         for(i = 0; i<=n; i++)
19             f[i] = i;
20         mark = 0, fNum = 0;
21         while(m--)
22         {
23             scanf("%d%d", &x, &y);
24             xx = find(x),  yy = find(y);
25             if(xx == yy)
26             {
27                 mark = 1;
28             }
29             else  {
30                 if (xx < yy)  f[yy] = xx;
31                 else  f[xx] = yy;
32             }
33         }
34         for(i = 1; i<=n; i++)
35             if(find(f[i]) == i)
36                 fNum ++;
37         if(mark == 1) printf("This is a graph.
");
38         else
39         {
40             if(fNum <= 1) printf("This is a tree.
");
41             else printf("This is a forest.
");
42         }
43     }
44     return 0;
45 }

View Code