模板：
#include#include #include using namespace std;#define MAXN 1024int fa[MAXN];int set_find(int d){ if(fa[d]<0)return d; return fa[d]=set_find(fa[d]);}void set_join(int x,int y){ x=set_find(x); y=set_find(y); if(x!=y)fa[x]=y;}int main(){ int n,m;//点数，边数 int x,y,i,sum; printf("输入点数、边数："); while(~scanf("%d%d",&n,&m)){ memset(fa,-1,sizeof(fa)); printf("输入边：\n"); while(m--){ scanf("%d%d",&x,&y); set_join(x,y); } sum=0; for(i=1;i<=n;++i) if(fa[i]==-1)++sum; printf("集合个数：%d\n",sum); printf("输入点数、边数："); } return 0;}
Problem A.
d.判断两个节点是否在同一个集合。
s.
c.
#include#include #include using namespace std;#define MAXN 1024int fa[MAXN];int x[MAXN],y[MAXN];bool repaired[MAXN];int set_find(int d){ if(fa[d]<0)return d; return fa[d]=set_find(fa[d]);}void set_join(int x,int y){ x=set_find(x); y=set_find(y); if(x!=y)fa[x]=y;}int main(){ int N,d; char str[3]; int p,q; while(~scanf("%d%d",&N,&d)){ memset(fa,-1,sizeof(fa)); memset(repaired,false,sizeof(repaired)); for(int i=1;i<=N;++i){ scanf("%d%d",&x[i],&y[i]); } while(~scanf("%1s",str)){ if(str[0]=='O'){ scanf("%d",&p); repaired[p]=true; for(int i=1;i<=N;++i){ if(repaired[i]&& ((x[p]-x[i])*(x[p]-x[i])+(y[p]-y[i])*(y[p]-y[i])<=d*d) ){ set_join(p,i); } } } else{ scanf("%d%d",&p,&q); p=set_find(p); q=set_find(q); if(p==q){ printf("SUCCESS\n"); } else{ printf("FAIL\n"); } } } } return 0;}
Problem B.
d.求某个集合中的节点数。
s.
c.
#include#include #include using namespace std;#define MAXN 30005int fa[MAXN];int set_find(int d){ if(fa[d]<0)return d; return fa[d]=set_find(fa[d]);}void set_join(int x,int y){ x=set_find(x); y=set_find(y); if(x!=y)fa[x]=y;}int main(){ int n,m,k; int x,y; int fa0;//节点0的父节点 int sum;// while(~scanf("%d%d",&n,&m)){ if(n==0&&m==0)break; memset(fa,-1,sizeof(fa)); for(int i=0;i
Problem C.
d.求集合个数。
s.
c.
#include#include #include using namespace std;#define MAXN 1024int fa[MAXN];int set_find(int d){ if(fa[d]<0)return d; return fa[d]=set_find(fa[d]);}void set_join(int x,int y){ x=set_find(x); y=set_find(y); if(x!=y)fa[x]=y;}int main(){ int T; int N,M; int A,B; int sum; scanf("%d",&T); while(T--){ memset(fa,-1,sizeof(fa)); scanf("%d%d",&N,&M); while(M--){ scanf("%d%d",&A,&B); set_join(A,B); } sum=0; for(int i=1;i<=N;++i){ if(fa[i]<0){ ++sum; } } printf("%d\n",sum); } return 0;}
Problem D.(带权的并查集，不错）
d.求假话的个数。
s.这是并查集很常见的题型。
对于A~B之间的和是S，其实可以理解成B比A-1大S；
这样和普通的并查集就很类似了。
c.
#include#include #include using namespace std;#define MAXN 200005int fa[MAXN];int sum[MAXN];//sum储存的是从父节点到当前节点的和int ans;int set_find(int d){ if(fa[d]<0)return d; int tmp=set_find(fa[d]); sum[d]+=sum[fa[d]]; return fa[d]=tmp;}void set_join(int x,int y,int w){ int x2=set_find(x); int y2=set_find(y); if(x2!=y2){ fa[y2]=x2; sum[y2]=w+sum[x]-sum[y]; } else{ if(sum[y]-sum[x]!=w)++ans; }}int main(){ int N,M; int A,B,S; while(~scanf("%d%d",&N,&M)){ memset(fa,-1,sizeof(fa)); memset(sum,0,sizeof(sum)); ans=0; while(M--){ scanf("%d%d%d",&A,&B,&S); set_join(A-1,B,S); } printf("%d\n",ans); } return 0;}
Problem E.
d.求假话的个数。
s.比较经典的并查集的题目，主要是要理解路径压缩的过程。
用0 1 2 分别表示A B C的关系。
0吃1,1吃2,2吃0.
注意这个编号都是以根结点为参照的，不是绝对的。
开一个sum数组，一开始这个数组为0，所有的点都是独立的，不是相连的，没有关系。
慢慢加入点之后，把有关系的合并在一起，并且编号的相对大小确定一个集合中的关系。
这题比较坑的地方就是，一定要单组输入，否则会WA。
c.
#include#include #include using namespace std;#define MAXN 50005int fa[MAXN];int sum[MAXN];//0吃1,1吃2,2吃0（都是相对根节点来说）int ans;int set_find(int d){ if(fa[d]<0)return d; int tmp=set_find(fa[d]); sum[d]+=sum[fa[d]]; sum[d]=sum[d]%3; return fa[d]=tmp;}void set_join(int D,int x,int y){ int x2=set_find(x); int y2=set_find(y); if(x2!=y2){ fa[y2]=x2; if(D==1){ sum[y2]=sum[x]-sum[y]; sum[y2]=(sum[y2]+3)%3; } else{ sum[y2]=sum[x]+1-sum[y]; sum[y2]=(sum[y2]+3)%3; } } else{ if(D==1){ if(sum[x]!=sum[y])++ans; } else{ if((sum[x]+1)%3!=sum[y])++ans; } }}int main(){ int N,K; int D,X,Y; scanf("%d%d",&N,&K);//好坑啊。。只能单组数据，否则wa //while(~scanf("%d%d",&N,&K)){ memset(fa,-1,sizeof(fa)); memset(sum,0,sizeof(sum)); ans=0; while(K--){ scanf("%d%d%d",&D,&X,&Y); if(X>N||Y>N){ ++ans; continue; } set_join(D,X,Y); } printf("%d\n",ans); //} return 0;}