tle三个点,c++并查集,qwq

P3367 【模板】并查集

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了


|