不会的看董晓

//拓展域并查集 
#include<bits/stdc++.h>
using namespace std;
int fa[21000];
int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}//寻找 
void he(int x,int y){fa[find(x)]=find(y);}//合并 
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(int i=1,x,y;i<=m;i++)
	{
		char c;cin>>c>>x>>y;
		if(c=='F')he(x,y);
		else he(y+n,x),he(x+n,y);
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(fa[i]==i)ans++;
	cout<<ans;
}

C123【模板】扩展域并查集 P1892 [BOI2003] 团伙

// 扩展域并查集 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,a,b,s;
int p[2005];

int find(int x){
  return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int x,int y){
  p[find(y)]=find(x);
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=2*n;i++) p[i]=i;
  for(int i=1;i<=m;i++){
    char ch; cin>>ch>>a>>b;
    if(ch=='F') merge(a,b);
    else{
      merge(a,b+n);
      merge(b,a+n);
    } 
  }
  for(int i=1;i<=n;i++)if(p[i]==i)s++;
  cout<<s;
}

有空的同学研究下这个代码为什么只得40分：

#include<bits/stdc++.h>
using namespace std;
//通过此题，深入了解体会并查集的作用：并查集只表达朋友关系，不表达敌对关系。
int fa[4100];
int findfa(int x){return (fa[x]==x)?fa[x]:fa[x]=findfa(fa[x]);}

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,tx,ty;char st[2];scanf("%s%d%d",st,&x,&y);
        if(st[0]=='F')
        {
            tx=findfa(x);ty=findfa(y);
            fa[tx]=ty;
            tx=findfa(x+n);ty=findfa(y+n);
            fa[tx]=ty;
        }
        else
        {
            tx=findfa(x);ty=findfa(y+n);
            fa[tx]=ty;
            tx=findfa(x+n);ty=findfa(y);
            fa[tx]=ty;
        }
        
    }
    int b[2100];for(int i=1;i<=n;i++)b[i]=findfa(i);
    sort(b+1,b+n+1);
    int ans=1;for(int i=2;i<=n;i++)ans+=(b[i]!=b[i-1]);
    printf("%d\n",ans);
    return 0;
}

C123【模板】扩展域并查集 P1892 [BOI2003] 团伙

// 扩展域并查集
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,a,b,s; int p[2005];

int find(int x){ return p[x]x?x:p[x]=find(p[x]); } void merge(int x,int y){ p[find(y)]=find(x); } int main(){ cin>>n>>m; for(int i=1;i<=2*n;i++) p[i]=i; for(int i=1;i<=m;i++){ char ch; cin>>ch>>a>>b; if(ch'F') merge(a,b); else{ merge(a,b+n); merge(b,a+n); } } for(int i=1;i<=n;i++)if(p[i]==i)s++; cout<<s; }</pre>
有空的同学研究下这个代码为什么只得40分：

#include<bits/stdc++.h>
using namespace std;
//通过此题，深入了解体会并查集的作用：并查集只表达朋友关系，不表达敌对关系。
int fa[4100];
int findfa(int x){return (fa[x]==x)?fa[x]:fa[x]=findfa(fa[x]);}

int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=2*n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x,y,tx,ty;char st[2];scanf("%s%d%d",st,&x,&y); if(st[0]=='F') { tx=findfa(x);ty=findfa(y); fa[tx]=ty; tx=findfa(x+n);ty=findfa(y+n); fa[tx]=ty; } else { tx=findfa(x);ty=findfa(y+n); fa[tx]=ty; tx=findfa(x+n);ty=findfa(y); fa[tx]=ty; } } int b[2100];for(int i=1;i<=n;i++)b[i]=findfa(i); sort(b+1,b+n+1); int ans=1;for(int i=2;i<=n;i++)ans+=(b[i]!=b[i-1]); printf("%d\n",ans); return 0; } </pre>