为什么这个题题解这么少啊
是不是大家都太强不屑于做板子题啊
//来自算法基础课
维护连通块size的并查集
一、初始化
void init() { for (int i=1; i<=n; i++) { fa[i] = i; size[i] = 1; } }
二、找祖源
int find(int x) { if(fa[x]==x) return x; else return fa[x] = find(fa[x]); }
三、合并连通块
void merge(int a,int b) { int x = find(a); int y = find(b); fa[x] = y; size[y] += size[x]; }
四、询问是否连通
bool ask(int a,int b) { return find(a)==find(b); }
特别注意：
size只有祖节点的有意义
要特别注意所有处理size的地方，都要“归根结底”
完整CODE
#include<bits/stdc++.h> #define read(x) scanf(“%d”,&x) using namespace std; const int N = 1e5+5; int n,m,a,b,fa[N], size[N]; string act; void init() { for (int i=1; i<=n; i++) { fa[i] = i; size[i] = 1; } } int find(int x) { if(fa[x]==x) return x; else return fa[x] = find(fa[x]); } void merge(int a,int b) { int x = find(a); int y = find(b); fa[x] = y; size[y] += size[x]; } bool ask(int a,int b) { return find(a)==find(b); } int main() { read(n),read(m); init(); while(m–) { cin>>act; if(act==“C”) { read(a),read(b); if(!ask(a,b)) merge(a,b); } else if(act==“Q1”) { read(a),read(b); ask(a,b) ? printf(“Yes\n”) : printf(“No\n”); } else { read(a); printf(“%d\n”,size[find(a)]); } } return 0; }
为什么这个题题解这么少啊
是不是大家都太强不屑于做板子题啊
//来自算法基础课
维护连通块size的并查集
一、初始化
void init() { for (int i=1; i<=n; i++) { fa[i] = i; size[i] = 1; } }
二、找祖源
int find(int x) { if(fa[x]==x) return x; else return fa[x] = find(fa[x]); }
三、合并连通块
void merge(int a,int b) { int x = find(a); int y = find(b); fa[x] = y; size[y] += size[x]; }
四、询问是否连通
bool ask(int a,int b) { return find(a)==find(b); }
特别注意：
size只有祖节点的有意义
要特别注意所有处理size的地方，都要“归根结底”
完整CODE
#include<bits/stdc++.h> #define read(x) scanf(“%d”,&x) using namespace std; const int N = 1e5+5; int n,m,a,b,fa[N], size[N]; string act; void init() { for (int i=1; i<=n; i++) { fa[i] = i; size[i] = 1; } } int find(int x) { if(fa[x]==x) return x; else return fa[x] = find(fa[x]); } void merge(int a,int b) { int x = find(a); int y = find(b); fa[x] = y; size[y] += size[x]; } bool ask(int a,int b) { return find(a)==find(b); } int main() { read(n),read(m); init(); while(m–) { cin>>act; if(act==“C”) { read(a),read(b); if(!ask(a,b)) merge(a,b); } else if(act==“Q1”) { read(a),read(b); ask(a,b) ? printf(“Yes\n”) : printf(“No\n”); } else { read(a); printf(“%d\n”,size[find(a)]); } } return 0; }
