hdu--1272--并查集||图的特点

其实觉得这个标题起得不太恰当...

但我又想并查集的操作是形成一颗树的结构这题的话是基于图来考虑比较好

因为是中文很容易理解题意而且我一般也不喜欢讲题意就想随便讲下应该注意和考虑的地方从我的角度来出发

这题一开始我的考虑方向是给出的这些点会不会形成回路就是成环如果出现了那就肯定是NO的

因为题目要求任意两点之间路径的唯一性如果成环那就会有多条路径的出现了

至于这个是否会成环的判断不难想到对于每次输入的x y 通过find操作得到他们各自的根结点然后比较根结点是否相同即可

但单纯这样操作还不够这样只是保证了不会出现成环的存在但不能保证只存在一个连通分量----也就是你可以看这组数据 1 2 3 4 0 0

那么其实是2个连通分量虽然是不存在环的

那么怎么判断连通分量是否只有一个呢？我们可以通过 father[x] == x来进行判断如果是1 就是Yes的了

******************这是一种方法

另外还有一种更巧妙的方法是

根据图的定义：在无向图中如果一个图既不含平行边与不含环那么称为简单图 --- 其实这题在我看来就是求是否给出的这些点能构成一张简单图

<但我的这概括并不严谨如果题目数据出现了平行边那么按照我的判断方法是错误的但是这题的数据中是没有平行边的>

边的数目+1 == 顶点的数目

OK 接下来直接上3份代码....

对于第二种方法我进行了使用 set与 vis数组的测试结果使用set的方法在时间上和内存上都消耗更大但是代码简洁

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 set<int>s;
 6 
 7 int main()
 8 {
 9     int x, y, side;
10     while (cin >> x >> y)
11     {
12         s.clear();
13         side = 0;
14         if (x == -1 && y == -1)
15             break;
16         if (x == 0 && y == 0)
17         {
18             cout << "Yes" << endl;
19         }
20         else
21         {
22             s.insert(x);
23             s.insert(y);
24             side++;
25             while (1)
26             {
27                 cin >> x >> y;
28                 if (!x && !y)
29                 {
30                     break;
31                 }
32                 s.insert(x);
33                 s.insert(y);
34                 side++;
35             }
36             if (s.size() == side + 1)
37                 cout << "Yes" << endl;
38             else
39                 cout << "No" << endl;
40         }
41     }
42     return 0;
43 }

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int size = 100010;
 7 bool vis[size];
 8 
 9 int main()
10 {
11     int x , y , side , point , mmax;
12     while( cin >> x >> y )
13     {
14         memset( vis , false , sizeof(vis) );
15         mmax = side = point = 0;
16         if( x==-1 && y==-1 )
17             break;
18         if( x==0 && y==0 )
19         {
20             cout << "Yes" << endl;
21         }
22         else
23         {
24             vis[x] = true;
25             vis[y] = true;
26             side ++;
27             mmax = max( mmax , max(x,y) );
28             while(1)
29             {
30                 cin >> x >> y;
31                 if( !x && !y )
32                 {
33                     break;
34                 }
35                 vis[x] = true;
36                 vis[y] = true;
37                 side ++;
38                 mmax = max( mmax , max(x,y) );
39             }
40             for( int i = 1 ; i<=mmax ; i++ )
41             {
42                 if( vis[i] )
43                     point ++;
44             }
45             if( point == side+1 )
46                 cout << "Yes" << endl;
47             else
48                 cout << "No" << endl;
49         }
50     }
51     return 0;
52 }

View Code

  1 //Runtime Error Stack OverFlow
  2 //#include "stdafx.h"
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 bool flag;
  8 int mmax;
  9 const int size = 100010;
 10 int father[size];
 11 bool vis[size];
 12 
 13 void init()
 14 {
 15     for (int i = 0; i <= size - 5; i++)
 16     {
 17         father[i] = i;
 18         vis[i] = false;
 19     }
 20 }
 21 
 22 int find(int x)
 23 {
 24     while( x != father[x] )
 25     {
 26         father[x] = father[ father[x] ];
 27         x = father[x];
 28     }
 29     return x;
 30 }
 31 
 32 /*
 33 int find(int x)
 34 {
 35     return x == father[x] ? x : father[x] = find(father[x]);
 36 }
 37 */
 38 
 39 void Union(int x, int y)
 40 {
 41     vis[x] = true;
 42     vis[y] = true;
 43     x = find(x);
 44     y = find(y);
 45     if (x != y)
 46     {
 47         //father[y] = x;
 48         father[x] = y;
 49     }
 50     else
 51     {
 52         flag = false;
 53     }
 54 }
 55 
 56 void getMax(int x, int y)
 57 {
 58     mmax = max(mmax, max(x, y));
 59 }
 60 
 61 int main()
 62 {
 63     int t = 0;
 64     int x, y, cnt;
 65     while (cin >> x >> y)
 66     {
 67         init();
 68         flag = true;
 69         cnt = mmax = 0;
 70         if (x == -1 && y == -1)
 71             break;
 72         if (x == 0 && y == 0)
 73         {
 74             cout << "Yes" << endl;
 75         }
 76         else
 77         {
 78             getMax(x, y);
 79             Union(x, y);
 80             while (1)
 81             {
 82                 cin >> x >> y;
 83                 if (!x && !y)
 84                     break;
 85                 getMax(x, y);
 86                 Union(x, y);
 87             }
 88             if (!flag)
 89             {
 90                 cout << "No" << endl;
 91             }
 92             else
 93             {
 94                 for (int i = 1; i <= mmax; i++)
 95                 {
 96                     if (vis[i] && father[i] == i)
 97                     {
 98                         cnt++;
 99                     }
100                 }
101                 if (cnt == 1)
102                     cout << "Yes" << endl;
103                 else
104                     cout << "No" << endl;
105             }
106         }
107         //if (t++)
108         //  cout << endl;
109     }
110     return 0;
111 }

View Code

这里题目有一点很坑的地方...

你按照它要求去输出空行反而是PE

单纯输出一行就AC了

卧槽了。。。。还好去看了discuss 真TM无语

这里的代码格式与我之前都有一些不同因为我这台机子 sublime编译环境搭建不好 =-= 我只能在sublime上写最近cfree编译有点迟钝..我就昨天下了个vs2013 然后今天是在vs上面进行编译的但vs吧会自动更正我的代码格式厌死了。。。可能可以自己设置让它不更正吧我也不知道没去找过

PS:打完一把如此惊心动魄的游戏之后才想起来了有1点忘记说了

这题我刚开始用递归版本的find的时候出现了 stack overflow 可能是递归层次太多了吧但TM看到了discuss里说将它改成 father[y] = x就可以了我试了下的确...

这应该是和数据有关系吧

然后我的做法是就采用了非递归版本的查找就是通过while来实现也是很容易写的

just follow your heart