### 正文

int find(int x) {
if (f[x]==x) {
return x;
}
return find(f[x]);
}


int find(int x) {
if (f[x]==x) {
return x;
}
return f[x]=find(f[x]);//路径压缩
}


void join(int x,int y) {
int nx=find(x),ny=find(y);//i、j 的最早祖先
f[nx]=ny;//并
}


### 拓展

#include <iostream>

using namespace std;
int n,m,ans;
char c;
int f[2001];

int find(int x) {
if (f[x]==x) {
return x;
}
return f[x]=find(f[x]);
}

void join(int x,int y) {
int nx=find(x),ny=find(y);
if (nx!=ny) {
f[nx]=ny;
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
cin>>n>>m;
for (int i=1;i<=2*n;i++) {
f[i]=i;
}
for (int i=1;i<=m;i++) {
cin>>c;
int t1,t2;
cin>>t1>>t2;
if (c=='F') {
join(t1,t2);
} else if (c=='E') {
join(t1+n,t2);
join(t2+n,t1);
}
}
for (int i=1;i<=n;i++) {
if (f[i]==i) {
ans++;
}
}
cout<<ans;
}


………

#include <iostream>
#include <cstdio>

using namespace std;
int f[300005];
int n,k,ans;

int sum=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') sum=sum*10+ch-48,ch=getchar();
return sum;
}

int find(int x) {
if (x==f[x]) {
return x;
}
return f[x]=find(f[x]);
}

void join(int x,int y) {
int nx=find(x),ny=find(y);
f[nx]=ny;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int x,y,z;
// cin>>n>>k;
for (int i=1;i<=3*n;++i)  {
f[i]=i;
}
for(int i=1;i<=k;++i)
{
// cin>>z>>x>>y;
if (x>n or y>n) {
ans++;
continue;
}
if(z==1)
{
if(find(x+n)==find(y) or find(x+n+n)==find(y)) {
ans++;
} else {
join(x,y);
join(x+n,y+n);
join(x+n+n,y+n+n);
}
} else if (z==2) {
if (x==y) {
ans++;
} else if (find(x)==find(y) or find(x+2*n)==find(y)) {
ans++;
} else {
join(x,y+n+n);
join(x+n,y);
join(x+n+n,y+n);
}
}
}
printf("%d\n",ans);
return 0;
}


p1551

p1536

p1621

p1892