首页 > 代码库 > poj1182 带权并查集
poj1182 带权并查集
带权并查集
利用路径压缩之后,所有点到祖先距离为1,合并集合只需要更改某一祖先的权值,那么只要权值具有相对性,只需要在getfather步骤里从父节点递归获取权值即可
#include<cstdio> #define rep(i,a,b) for (int i=a;i<=b;++i) using namespace std; int n,ans,a,x,y,q,w,k; int fa[60000]; int dis[60000]; int getfather(int x) { if (fa[x]==x) return x; int t=fa[x]; fa[x]=getfather(t); dis[x]=(dis[x]+dis[t])%3; return fa[x]; } void Union(int a,int b,int father,int son,int dist) { dis[b]=(-dis[son]+dis[father]+dist+3)%3; fa[b]=a; } int main() { scanf("%d%d",&n,&k); rep(i,1,n) fa[i]=i,dis[i]=0; ans=0; rep(i,1,k) { //printf("%d\n",ans); scanf("%d%d%d",&a,&x,&y); --a; if (x>n || y>n) {++ans;continue;} q=getfather(x);w=getfather(y); if (q==w){if (!((a==0 && dis[x]==dis[y]) || (a==1 && (dis[x]-dis[y]+1)%3==0))) ++ans;} else Union(q,w,x,y,a); } printf("%d\n",ans); return 0; }
poj1182 带权并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。