并查集

P1955 程序自动分析（并查集 + 离散化）

P1955 [NOI2015] 程序自动分析 - 洛谷

并查集 + 离散化，和算法竞赛那本书的例题一模一样。

思路：先建立并查集，把所有 e == 1（相等）的约束合并起来。因为还需要判断不相等的情况，所以得跑两轮——第二轮遇到 e == 0 且两个数已经在同一集合里，就说明前面的约束和它矛盾，直接 break。

变量范围到 1e9 而约束只有 1e5 条，所以要先离散化，把出现过的数映射到 1..m 的连续编号上。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

const int maxn=100005;

struct Constraint{
    int x,y,e;
};

int fa[maxn*2];
vector<int> nums;
vector<Constraint> cons;

void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

int get(int x){
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}  //查找+路径压缩

int find_id(int val){
    return lower_bound(nums.begin(),nums.end(),val)-nums.begin()+1;
}  //离散化

void merge(int x,int y){
    fa[get(x)]=get(y);
}

void solve(){
    int n; cin>>n;
    nums.clear(); cons.clear(); //清空上组数据

    for(int i=0;i<n;i++){
        int x,y,e; cin>>x>>y>>e;
        cons.push_back({x,y,e});
        nums.push_back(x); nums.push_back(y);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    //去重+排序

    int m=nums.size();

    init(m);

    for(int i=0;i<n;i++){
        if(cons[i].e==1){
            int id_x=find_id(cons[i].x);
            int id_y=find_id(cons[i].y);
            merge(id_x,id_y);
        }
    }

    bool is_possi=true;
    for(int i=0;i<n;i++){
        if(cons[i].e==0){
            int id_x=find_id(cons[i].x);
            int id_y=find_id(cons[i].y);

            if(get(id_x)==get(id_y)){
                is_possi=false;
                break;
            }
        }
    }

    if(is_possi) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

这道题顺带学到的：

  • 去重方法：sort 之后 nums.erase(unique(nums.begin(), nums.end()), nums.end())，是离散化的标准起手式，之后就能直接用 lower_bound 定位。
  • 多组数据要记得清空：nums.clear(); cons.clear(); 放在 solve() 开头，别靠全局变量残留。注意 fa 数组不需要清空，因为 init(m) 会重新覆盖到 m 位。
  • 两轮处理的顺序不能颠倒：必须先合并完所有相等关系，再检查不等关系，否则合并是「边检查边做」的，会漏判。

附：LeetCode 1353 最多可以参加的会议数目

1353. 最多可以参加的会议数目 - 力扣

这道题其实似乎用不到并查集，但是无伤大雅。

贪心 + 优先队列：优先参加结束时间相对早的会议，要不然后面来不及参加了。

怎么找到结束时间最早的会议？ 用优先队列。priority_queue 的小根堆写法是笔者之前在做合并果子这道题的时候学的：

1
priority_queue<int,vector<int>,greater<int>> q;

队列里只保存 endDay。按开始时间排序后，用 day 从左往右扫，每天把当天开始的会议全部入队，然后弹掉已经过期的（q.top() < day），再取队首那个结束最早的参加掉——参加一场，ans 加一。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin>>n;

    vector<vector<ll>> events(n);
    for(int i=0;i<n;i++){
        ll l,r; cin>>l>>r;
        events[i]={l,r};
    }

    sort(events.begin(),events.end());

    priority_queue<int,vector<int>,greater<int>> q;
    int i=0;
    int day=1;
    int ans=0;

    while(i<n || !q.empty()){
        while(i<n && events[i][0]==day){
            q.push(events[i][1]);
            i++;
        }

        while(!q.empty()&& q.top()<day) q.pop();

        if(!q.empty()){
            q.pop();
            ans++;
        }

        day++;
    }

    cout<<ans<<endl;
    return 0;
}

总结

  • 并查集的核心是 get 的路径压缩和 merge 的方向，模板本身很短，难点在于看出题目里的「等价关系」。
  • 一旦值域大而数据量小，先想离散化；sort + unique + lower_bound 是固定套路。
  • 需要判断「不相等」时，先合并全部相等、再统一检查不等，两轮走。
  • 小根堆 priority_queue<int,vector<int>,greater<int>> 是「每次取最小」场景的通用工具，贪心题里出现频率极高。