网易互娱 开发11号3道笔试题题解

2.并查集  集合操作

将X独立出来时，如果X是集合的祖先，需要从集合中再选一个当祖先

#include <bits/stdc++.h>

//freopen("temp.in","r",stdin);#include "utils.cpp"
using namespace std;
#define UF(i,start,end) for(auto i=start;i<end;i++)
#define DF(i,start,end) for(auto i=start;i>=end;i--)
int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回
string rs(){string s;cin>>s;return s;}
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<bool> vecb;
typedef vector<string> vecs;
typedef vector<vector<int>> vveci;


template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){
for(auto t:v)
os<<t<<" ";
os<<endl;
return os;
}
template <typename T>
ostream &print(ostream &os,const T &t){
return os<<t<<endl;
}
template <typename T,typename... Args>
ostream &print(ostream &os,const T &t,const Args&... rest){
os << t <<" ";
return print(os,rest...);
}
template <typename T,typename... Args>
void PR(const T &t,const Args&... rest){
print(cout,t,rest...);
}


//并查集
const int MAX_SIZE = 10005;
int f[MAX_SIZE];//祖先节点
int find_root(int v){
if(f[v]==v) return v;
int z = find_root(f[v]);//找父亲的祖先
f[v] = z;
return z;
}
int N,M;
void my_print(){
UF(i,1,N+1){
cout<<f[i]<<" ";
}
cout<<endl;
}
int main(){
//PR(get_next("ababc"));
freopen("temp.in","r",stdin);
//freopen("temp.out", "w", stdout);
//test();
string s1,s2;
int T;

int X,Y;
cin>>T;
while(T--){
memset(f,-1,sizeof f);//能初始化成功吗?

cin>>N>>M;
int OP;
UF(i,1,N+1) f[i]=i;
UF(i,0,M){
cin>>OP;
if(OP==1){
cin>>X>>Y;
int a = find_root(X),b = find_root(Y);
if(a!=b){
f[b] = a;//令Y的祖先  认X的祖先为  祖先
}
//my_print();
}else{
cin>>X;
if(OP==2){
//如果X是祖先，就让它的子孙重新认一个
int new_z=-1;
UF(i,1,N+1){
if(i!=X and find_root(i)==X){
new_z = i;
}
}
UF(i,1,N+1){
if(i!=X and find_root(i)==X) f[i]=new_z;
}
f[X]=X;
//my_print();
}else{
int ans = 0;
X = find_root(X);
UF(i,1,N+1){
if(find_root(i)==X) ans++;
}
PR(ans);
}
}
}

}

//cout<<setprecision(2)<<ans<<endl;       设置输出总位数
//cout<<fixed<<setprecision(2)<<ans<<endl;       设置小数点后两位输出
return 0;

}
3.  最小错序排列.. 搜索--剪枝