并查集

模板题：
此题非常经典，是不带权的并查集模板

P1551 亲戚

注意：
合并是把根节点合并，不是中途合并，不然会发生断路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int totalSet[5005];
int find_set(int a){
    if(totalSet[a]==a){
        return a;
    }
    totalSet[a]=find_set(totalSet[a]);
    return totalSet[a];
}
void add_set(int a,int b){//把a分支并入b
    a=find_set(a),b=find_set(b);
    totalSet[a]=totalSet[b];
}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
        totalSet[i]=i;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add_set(a,b);
    }
    for(int i=0;i<p;i++){
        int a,b;
        cin>>a>>b;
        find_set(a);
        find_set(b);
        if(totalSet[a]==totalSet[b])
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

P1621 集合

并查集加素数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
int a,b,p,totalSet[100005];
int find_set(int a);
void add_set(int a,int b);
bool noP[100005];
vector<int> primers;
int main(){
    cin>>a>>b>>p;
    for(int i=1;i<=b;i++)//初始化
        totalSet[i]=i;
    
    for(int i=2;i<=b;i++){
        if(noP[i]==0)
            primers.push_back(i);
        for(int j=0,len=primers.size();j<len;j++){
            if(i*primers[j]>b)
                break;
            noP[i*primers[j]]=1;
        }
    }
    //得到b范围内的全部素数
    for(int i=0,len=primers.size();i<len;i++){
        if(primers[i]<p)
            continue;
        int count=2;
        while(primers[i]*count<=b){
            if(primers[i]*count>=a){
                add_set(primers[i],primers[i]*count);
            }
            count++;
        }
    }
    int ans=0;
    for(int i=a;i<=b;i++){
        if(totalSet[i]==i)
            ans++;
    }
    cout<<ans;
    return 0;
}


int find_set(int a){
    if(totalSet[a]==a){
        return a;
    }
    totalSet[a]=find_set(totalSet[a]);
    return totalSet[a];
}
void add_set(int a,int b){//把a分支并入b
    a=find_set(a),b=find_set(b);
    totalSet[a]=totalSet[b];
}

二叉堆

P3378 堆

STL形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
priority_queue <int,vector<int>,greater<int>> q;
int main(){
    int n;
    cin>>n;
    while(n--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            q.push(x);
        }else if(op==2){
            cout<<q.top()<<endl;
        }else{
            q.pop();
        }
    }
    return 0;
}

数组模拟二叉堆
关键点：理解插入操作是不断和父节点比大小 删除操作是和子节点比大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int q[MAXN],tail=1;

void push(const int& x){
    q[tail]=x;
    int nowIndex=tail++;
    while(nowIndex>=2){
        if(q[nowIndex/2]>q[nowIndex]){
            swap(q[nowIndex/2],q[nowIndex]);
            nowIndex/=2;
        }else
            break;
    }
}
int top(){
    return q[1];
}
void pop(){
    // q[tail--]=0;
    tail--;
    q[1]=q[tail];
    int i=1;
    while(2*i<tail){//保证有左子节点
        int ls = 2*i;
        int rs = ls+1<tail?ls+1:ls;
        int mins = q[ls]<q[rs]?ls:rs;
        if(q[i]<q[mins])
            break;
        swap(q[i],q[mins]);
        i = mins;
    }
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            push(x);
        }else if(op==2){
            cout<<top()<<endl;
        }else{
            pop();
        }
    }
    return 0;
}