公司商业网站怎么做,济南网站自然优化,备案 网站下线,使用php做的网站有哪些例题#xff1a;
#xff08;1#xff09;Acwing 836.合并集合 并查集就是把每一个集合看成一棵树#xff0c;记录每个节点的父节点。合并集合就是把一棵树变成另一棵树的子树#xff0c;即把一棵树的父节点变为另一棵树的父节点的儿子。查询是否在同一集合就是看他们的根…例题
1Acwing 836.合并集合 并查集就是把每一个集合看成一棵树记录每个节点的父节点。合并集合就是把一棵树变成另一棵树的子树即把一棵树的父节点变为另一棵树的父节点的儿子。查询是否在同一集合就是看他们的根节点是否相同。在查找过程中可以路径加速把每个点直接连到根节点。
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 1e510;
int p[N];
int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];
}
int main()
{int n,m;scanf(%d%d, n, m);for(int i 1;in;i){p[i] i;}for(int i 0;im;i){char op[2];int x,y;scanf(%s%d%d,op,x,y);if(op[0] M){p[find(x)] find(y);}else{if(find(x)find(y)) printf(Yes\n);else printf(No\n);}}return 0;
}
(2) Acwing 837.连通块中点的数量 并查集板子题把每个联通块当成一棵树连边操作就等于将联通块合并查询是否在同一个联通块中就等于查询其根节点是否相同询问数量需要额外维护一个size数组每次合并时根节点的size要加上被合并的根节点的size。如果合并时两个节点的根节点相同则无需合并否则size会加倍。
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 1e510;
int sz[N],p[N];
int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];
}
int main()
{int n,m;scanf(%d%d, n, m);for(int i 1;in;i){p[i] i;sz[i] 1;}for(int i 0;im;i){char op[2];int x,y;scanf(%s,op);if(op[0] C){scanf(%d%d, x, y);if(find(x)!find(y)){sz[find(x)] sz[find(y)];p[find(y)] find(x);}}else if(op[1] 1){scanf(%d%d, x, y);if(find(x) find(y)) printf(Yes\n);else printf(No\n);}else{scanf(%d, x);printf(%d\n,sz[find(x)]);}}return 0;
}
3AcWing 240. 食物链 由于是一个环形食物链因此可以使用带权并查集记录每个节点到根节点的距离通过%3所得的数判断两者间的关系。具体代码有注释。
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 1e510;
int d[N],p[N];
int find(int x){if(p[x]!x){int t find(p[x]);//把该点的父节点以上的所有节点全部连到根节点d[x] d[p[x]];//此时d[p[x]]就是p[x]到根节点的距离p[x] t;//p[x]连到根节点}return p[x];
}
int main()
{int n,m,res 0;scanf(%d%d, n, m);for(int i 1;in;i){p[i] i;}while (m -- ){int s,x,y;scanf(%d%d%d,s, x, y);if(xn||yn){res;continue;}else if(s 1){int px find(x),py find(y);if(px py){if((d[x]-d[y])%3) res;//同类则模0continue;}else{p[px] py;d[px] d[y] - d[x];}}else{int px find(x),py find(y);if(px py){if((d[x]-d[y]-1)%3) res;//可能存在一正一负因此不能1continue;}else{p[px] py;d[px] d[y] - d[x] 1;}}}printf(%d,res);return 0;
}
练习1Leetcode 128.最长相关序列 把数组里的每一个数看做一个节点而每个节点可以与权值比自己本身权值小1的节点相连。对于数组中的每个数如果权值比他小1的数在哈希表中存在并且两者不具有相同的根结点时由于数组中不存在重复元素且每次只会把大的数接在小的数后面因此两者集合必然是连续的。所以先进行去重然后开始建树由于存在负数因此利用哈希表储存每个数的下标防止访问越界。问题可以转化为最大的联通块中点的数量。
class Solution {
public:unordered_mapint,int x;int p[100010],sz[100010];int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];}int longestConsecutive(vectorint nums) {sort(nums.begin(),nums.end());nums.erase(unique(nums.begin(),nums.end()),nums.end());int n nums.size();for(int i 1;in;i){x[nums[i-1]] i;p[i] i;sz[i] 1;}for(int i 0;in;i){if(x[nums[i]-1]find(x[nums[i]-1]) ! find(x[nums[i]]) ){sz[find(x[nums[i]-1])] sz[find(x[nums[i]])];p[find(x[nums[i]])] find(x[nums[i]-1]);}}int ans 0;for(int i 0;in;i){if(p[x[nums[i]]] x[nums[i]]) ans max(ans,sz[x[nums[i]]]);}return ans;}
};
2Leetcode 684.冗余连接 没做出来。。 遍历每条边如果该边的两个端点属于一个集合内那么就说明这条边导致了一个环的构成。返回这条边。否则把两个端点加到同一个集合内。由于题目规定只会多出一条边只会存在一个环因此出现的这条边一定是构成环的最后一条边因为假如后面还存在能构成环的边则不满足只有一个环的条件因此这条边就是构成环的最后一条边。
class Solution {
public:int p[1010];int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];}vectorint findRedundantConnection(vectorvectorint edges) {int n edges.size();for(int i 1;in;i) p[i] i;for(auto c:edges){int a find(c[0]),b find(c[1]);if(ab) return{c[0],c[1]};else{p[a] b;}}return {0,0};}
};
(3)Leetcode 1202.交换字符串中的元素 并查集应该不是最佳解。。不过没想出来啥别的方法。。 第一步把所有能交换的位置构成一个集合。第二步遍历字符串把每个字母加入其根节点映射的优先队列可以自动按字典序排序第三步遍历字符串用一个空字符串记录结果。在每个字母对应的位置放上其根节点对应的优先队列中第一个字母按字典序最小的字母然后该元素出队。
class Solution {
public:int p[100010];int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];}string smallestStringWithSwaps(string s, vectorvectorint pairs) {unordered_mapint,priority_queueint,vectorint,greaterint x;int n s.length();for(int i 0;in;i) p[i] i;for(auto c:pairs){int a find(c[0]),b find(c[1]);if(a!b) p[a] b;} for(int i 0;in;i) x[find(i)].push((int)s[i]);string res ;for(int i 0;in;i){char ch (char)x[find(i)].top();x[find(i)].pop();resch;}return res;}
};
(4)Leetcode 886.可能的二分法 判断二分图的最好方法并不是并查集但是。。用并查集没做出来。。 把每一个人的关系不好的人放入一个集合中如果这个集合的人里面有人跟该人的根节点相同说明其属于同一个集合不成立反之则把他们加入同一个集合。
class Solution {
public:unordered_mapint,vectorint x;int p[2010];int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];}bool possibleBipartition(int n, vectorvectorint dislikes) {if(!dislikes.size()) return true;for(auto c:dislikes){x[c[0]].push_back(c[1]);x[c[1]].push_back(c[0]);}for(int i 1;in;i) p[i] i;for(int i 1;in;i){if(x[i].empty()) continue;int a find(i),b find(x[i][0]);for(auto c:x[i]){if(find(c) a) return false;p[find(c)] b;}}return true;}
};
5) P8686 [蓝桥杯 2019 省 A] 修改数组 。。。其实还是没太理解。。 首先把每一个数的根节点设为其本身然后对于每次输入的数如果其根节点为本身说明其第一次出现因此把根节点更新为原先的根节点1否则查找其根节点由于每次都加1因此 从 其本身 到 其根节点-1 都已经出现过然后输出根节点并且把 根节点1 作为根节点的新父节点这个父节点有可能还会有父节点但并不影响可以理解为两条链相连成为一条更长的新链 初始化时要把后面的节点一起初始化否则更新时由于后续某些节点的根节点变为0就会出错。。
#include iostream
using namespace std;
const int N 100010;
typedef long long ll;
ll p[N];
ll find(ll x){if(p[x]!x) p[x] find(p[x]);return p[x];
}
int main(int argc, char** argv) {ll n;scanf(%d,n);for(int i 1;i100010;i) p[i] i;for(int i 1;in;i){ll x;scanf(%lld,x);printf(%lld ,find(x));p[find(x)] find(x) 1;}return 0;
}
7洛谷 P1111 修复公路 。。很烦。。 联通块的个数为1时就能完全通车。首先按照时间排序分清路的条数和村庄的个数然后遍历每一条路假如两个路边上的村庄共用一个根节点则无视否则联通块数-1把两个村庄联通。每次判断所有联通块是否只剩一个如果是则输出当前时间戳如果最后还剩不止一个联通块则输出-1。这里判断联通块个数不需要每一次都遍历只需要维护联通块个数即可因为一开始每一个村庄就是一个联通块
#include iostream
#include algorithm
using namespace std;
const int N 1010,M 100010;
struct Node{int x,y,t; bool operator (Node a){return t a.t;}
}road[M];
int p[N];
int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];
}
int main(int argc, char** argv) {int n,m;scanf(%d%d,n,m);int res n; for(int i 1;in;i) p[i] i;for(int i 0;im;i){scanf(%d%d%d,road[i].x,road[i].y,road[i].t);}sort(road,roadm);bool flag 0;for(int i 0;im;i){int a find(road[i].x),b find(road[i].y),c road[i].t;if(a b) continue;else{res--;if(res1){printf(%d,c);flag 1;break;}p[a] b;}}if(!flag) printf(-1);return 0;
}
(8)洛谷 P1455 搭配购买 一个缝合题01背包加并查集。。01背包写的很差还是不太会用滚动数组。。后面再补一下吧。。 用并查集把多个商品合成为一个商品根节点代表商品本身。01背包不用滚动数组会MLE。更新时注意是更新根节点的价格和价值因为是连接根节点。
#include iostream
using namespace std;
const int N 1e410;
int w[N],v[N],p[N],f[N];
struct Node{int w,v;
}shop[N];
int find(int x){if(p[x]!x) p[x] find(p[x]);return p[x];
}
int main(int argc, char** argv) {int n,m,w1;scanf(%d%d%d,n,m,w1);for(int i 1;in;i){scanf(%d%d,w[i],v[i]);p[i] i;}for(int i 0;im;i){int a,b;scanf(%d%d,a,b);a find(a),b find(b);if(ab) continue;p[a] b;w[b] w[a];v[b] v[a];}int cnt 1;for(int i 1;in;i){if(p[i]!i) continue;shop[cnt].w w[i];shop[cnt].v v[i];cnt;}for(int i 1;in;i){for(int j w1;jshop[i].w;j--){f[j] max(f[j],f[j-shop[i].w] shop[i].v);}}printf(%d,f[w1]);return 0;
}
9P3420 SKA-Piggy Banks 虽然做出来了。。但是感觉还是搞不太明白。。 这道题之所以可以用并查集的原因并不是因为罐子之间存在钥匙联系而是一个罐子只有一个钥匙且在另一个罐子里但一个罐子可以装多把钥匙。因此我们每次把钥匙对应的罐子连在存放钥匙的罐子后面则打开根节点的罐子就可以打开所有罐子。因此一个集合内的罐子就一定只需要打开一个罐子题目也就改为求联通块的数目。因此这道题用并查集可以做的原因其实是每个钥匙唯一且对应了一个罐子。假如题目改为第i个数代表第i个罐子存放了第ai个罐子的钥匙这道题就不能用并查集做了。。https://www.luogu.com.cn/discuss/684322https://www.luogu.com.cn/discuss/684322 这是比较专业的解答。。。我只能用自己的角度去解释。。解释的不太好。。
10P1196 [NOI2002] 银河英雄传说 。。确实是挺难的。。 为了查询两个战舰之间的战舰数目我们维护每一个战舰到根节点的距离这样两个战舰之间的战舰数目就是到根节点的距离差-1。而由于我们维护到根节点的距离还需要知道当前集合内的战舰数量因此还需要维护一个数组用来记录每个集合根节点下的战舰数。当然由于每个节点都没法在合并时就被更新因此我们可以在find函数时对每个节点进行更新。
#include iostream
using namespace std;
const int N 30010;
int p[N],dis[N],num[N];
int find(int x){if(p[x]!x){int k p[x]; p[x] find(p[x]);dis[x] dis[k];num[x] num[p[x]];}return p[x];
}
int main(int argc, char** argv) {int t;scanf(%d,t);for(int i 1;i30000;i){p[i] i;num[i] 1;}while(t--){char op[2];scanf(%s,op);int x,y;scanf(%d%d,x,y);if(op[0] M){x find(x);y find(y);if(x!y){p[x] y;dis[x] num[y];num[y] num[x];num[x] num[y];}}else{if(find(x) find(y)) printf(%d\n,abs(dis[x] - dis[y])-1);else printf(-1\n);}}return 0;
}
