The_NewBoy @ 2021-05-12 18:50:13
这题是要写快读吗? 我也不知道咋搞
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define zyq 500500
#define xzy 500500
using namespace std;
int find(int);
void join(int,int);
int n,m;
int fa[zyq];
int z,x,y;
int px,py;
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n+1;i++) fa[i]=i;
for(int i=1;i<=m;i++){
cin>>z>>x>>y;
if(z==1){
join(x,y);
}
if(z==2){
if(find(x)==find(y)){
cout<<"Y\n";
}
else cout<<"N\n";
}
}
return 0;
}
int find(int x){
if(fa[x]==x)
return x;
return find(fa[x]);
}
void join(int x,int y){
if(find(x)!=find(y))
fa[find(y)]=find(x);
}
by AladV @ 2021-05-12 18:51:14
让我猜猜,你加按秩合并没有?
by Terraria @ 2021-05-12 18:51:32
@kkkscr__03 试试压缩路径?
by The_NewBoy @ 2021-05-12 18:52:16
了解了
我去试下
谢谢
by EDqwq @ 2021-05-12 18:52:47
@kkkscr__03 请加上fa[x] = find(fa[x])
这句话,这是路径压缩 是必不可少的
by The_NewBoy @ 2021-05-12 18:54:19
谢谢!
我A了