软件园二期做网站的公司,2023年的新闻十条,便宜的购物网站排名,大连建设银行招聘网站食物链 核心思想#xff1a;带权并查集 用距根节点和距离表示与根节点的关系 求距离 #includeiostreamusing namespace std;const int N50010;int n,m;int p[N],d[N];//找到祖宗节点(路径压缩) 并求出对应距离int find(int x){if(p[x]!x){int up[x]; //保存旧父节点…食物链 核心思想带权并查集 用距根节点和距离表示与根节点的关系 求距离 #includeiostreamusing namespace std;const int N50010;int n,m;int p[N],d[N];//找到祖宗节点(路径压缩) 并求出对应距离int find(int x){if(p[x]!x){int up[x]; //保存旧父节点d[x] d[u];p[x] find(p[x]); //路径压缩 所有节点指向祖宗节点}return p[x];}int main(){cinnm;for(int i1;in;i) p[i]i; //初始化int res0;while(m--){int t,x,y;cintxy;if(xn||yn) res; //超出范围else{int pxfind(x),pyfind(y); //找到xy的祖宗节点if(t1){ //说明是同类 判断对错if(pxpy (d[x]-d[y]) % 3!0) res; //说明在一个并查集中,且xy不同类(距离不是3的倍数)else if (px ! py){ //不在一个并查集p[px] py; //将x的祖宗节点的父节点改成y的祖宗节点d[px] d[y] - d[x]; //xy同类-路径长度推算d[y]-d[x]}}else{ //说明是异类 判断对错if(pxpy (d[x]-d[y]-1)%3!0) res; //说明在一个并查集中,且x不能吃y(d[x]!d[y]13*k) else if (px ! py){p[px] py; d[px] d[y] 1 -d[x]; //x吃y-推算d[px]长度}}}}coutres;}
