求助!并查集模板题 为什么我的才30?

P3367 【模板】并查集

泰山飞狐 @ 2019-02-13 10:35:48

include<iostream>

include<cstdio>

include<cstdlib>

include<cmath>

include<algorithm>

using namespace std; int n,m,f[10001]; int read(){ int ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } int getf(int v) { return f[v]==v ?v:getf(f[v]); } int merge(int u,int v) { int t1=getf(u),t2=getf(v); if(t1!=t2) { return 1; } return 0; } int main() { n=read();m=read(); int i; for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++) { int opt,x,y; opt=read();x=read();y=read(); if(opt==1) { f[y]=x; } if(opt==2) { if(merge(x,y)) cout<<"N"<<endl; else cout<<"Y"<<endl; } } return 0; }


by nofall @ 2019-02-13 10:37:56

希望更丰富的展现?使用Markdown


by xunJason @ 2019-02-13 10:42:25

getf函数return时顺便将所有儿子指向祖先


by 挽忆 @ 2019-02-13 10:42:50

并查集那一段

return f[v]==v ?v:getf(f[v]);

是不是要改为

return f[v]==v ?v:f[v]=getf(f[v]);

by Catalan1906 @ 2019-02-13 10:42:59

@育秀中学leo

fa[x]=y

还行哦


by 挽忆 @ 2019-02-13 10:43:52

目测已解决


by YZHX @ 2019-02-13 11:07:03

@育秀中学leo 有个人名字和你差不多 @leo101


by YZHX @ 2019-02-13 11:07:16

leo大佬


by powerLEO101 @ 2019-02-13 11:08:55

。。。 Orz yzhx


by 泰山飞狐 @ 2019-02-14 22:14:01

已经解决 谢谢各位!~~~~


|