首页 > 代码库 > hdu--1856--并查集的离散化处理
hdu--1856--并查集的离散化处理
这题 花了我好久时间啊 卧槽 ....
但是 也越来越迷茫了 有点觉得 acm带给了你什么？
现在 已经不再向当初在自己OJ那样刷题 来追求ranklist =-=
我们应该是获得思维上的提高 那么 刷题 不是感觉回到了 高三时代吗? 只是换了种形式
所以 我也不知道了
现在 每天 有时间 就尽量能做到1 2个好题
**********************************************碎碎念
这题的数据很大啊 但内存又给了足足有102400 K 太大了 一下子 把题目难度给降低了 这样使得你即使去开10000000的数组都可以
但我们应该是离散化它 去开一个100000的数组来实现
发现 我线段树的时候 也遇到过离散化 但我至今处理不好 W T F
所以 这个离散化 又花了好久 但我觉得相比 线段树的处理 简单多了
一般来说 对于 离散化处理 我们就是将输入的数据X Y存入一个数组 这样即使数据是 1 200000 34 23我们就需要一个长度为4的数组 sort一遍后变成了1 23 34 200000
那么 这时候 200000已经映射成为----->4了 我们把它当作4来处理了 同时 这边你可能会遇到情况是 给你的数据中出现了相同的数字 没关系 我们只要再sort一遍之后 再进行下
unique()函数 就可以 注意 它返回的是指针 所以需要-arr（假设这是数组的名字)那么就可以了
这题 当时 我在想输入X Y的时候 那么是要将X Y关联起来的 那么 一起存入一个结构体中可以了 好像C++中提供一个叫pair的对 也能实现这个功能 但我用不好
然后 当我们unique完成后 此时数组中的元素都是独一无二的了 然后我们将其进行映射 即map<int,int>mp mp[1] = 1 mp[23] = 2 mp[34] = 3 mp[200000] =4这样的结果得到
最后 就如同普通并查集一样了for i 0->n do find && union OK
对于 这个find提一句 一般 最好还是都加上路径压缩 这个实在节约了好多时间啊 还有对于 union操作 一般是会多一步rank[x]与rank[y]的判断 你可以把它理解为X 和 Y根结点深度的比较 一般会选择 将深度小的根节点接到大的根节点下面 但似乎 有时候 任意操作 对时间影响并不是很大吧
噢 对了 对于 这题 当N=0的时候 要输出1 因为1对都没有 那就是有单个 那就是1个人 这点题目中 提到了
我想 以后的每篇博客 我都尽量多点废话 =-= 可能也就持续 3分钟的热度 我也不知道。。
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 using namespace std; 5 6 int n, ans; 7 const int size = 100010; 8 struct data 9 {10 int x, y;11 }node[size];12 int arr[size*2];13 int father[size];14 int Rank[size];15 map<int, int>mp;16 17 void init()18 {19 mp.clear();20 for (int i = 0; i <=n; i++)21 {22 father[i] = i;23 Rank[i] = 1;24 }25 }26 27 int find(int x)28 {29 return x == father[x] ? x : father[x] = find(father[x]);30 }31 32 void Union(int x, int y)33 {34 if (Rank[x] >= Rank[y])35 {36 Rank[x] += Rank[y];37 father[y] = x;38 if (Rank[x] > ans)39 ans = Rank[x];40 }41 else42 {43 Rank[y] += Rank[x];44 father[x] = y;45 if (Rank[y] > ans)46 ans = Rank[y];47 }48 }49 50 int main()51 {52 cin.sync_with_stdio(false);53 int x, y, num, cnt;54 while (cin >> n)55 {56 init();57 cnt = 0;58 ans = 1;59 for (int i = 0; i<n; i++)60 {61 cin >> x >> y;62 node[i].x = x;63 node[i].y = y;64 arr[cnt++] = x;65 arr[cnt++] = y;66 }67 sort(arr, arr + cnt);68 cnt = unique(arr, arr + cnt) - arr;69 for (int i = 0; i<cnt; i++)70 {71 mp[ arr[i] ] = i;72 }73 for (int i = 0; i<n; i++)74 {75 x = mp[ node[i].x ];76 y = mp[ node[i].y ];77 x = find(x); 78 y = find(y);79 if (x != y)80 {81 Union(x, y);82 }83 }84 cout << ans << endl;85 }86 return 0;87 }
today:
只怕爱情的箴言听太多 用脑筋多余用情
经验是钥匙而不是枷锁
每一次恋爱都好像没受伤过
像孩子一样天真地享受花火 想做什么就做