首页 > 代码库 > hdu--1272--并查集||图的特点
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 else21 {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 else39 cout << "No" << endl;40 }41 }42 return 0;43 }
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 else23 {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 else48 cout << "No" << endl;49 }50 }51 return 0;52 }
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 else104 cout << "No" << endl;105 }106 }107 //if (t++)108 // cout << endl;109 }110 return 0;111 }
这里 题目 有一点很坑的地方...
你按照它要求 去输出空行 反而是PE
单纯输出一行 就AC了
卧槽了。。。。 还好去看了discuss 真TM无语
这里的代码格式 与我之前都有一些不同 因为我这台机子 sublime编译环境搭建不好 =-= 我只能在sublime上写 最近cfree编译有点迟钝..我就昨天下了个vs2013 然后今天是在vs上面进行编译的 但vs吧 会自动更正我的代码格式 厌死了。。。 可能 可以自己设置 让它不更正吧 我也不知道 没去找过