【題目鏈接】

洛谷 P1955 [NOI2015] 程序自動分析

【題目考點】

1. 并查集

2. 離散化

【解題思路】

多組數據問題，對于每組數據，有多個$x_i=x_j$或$x_i\ne x_j$的約束條件。

所有相等的變量構成一個集合，不相等的變量在不同的集合。可以使用并查集表示集合。
該題的變量編號$i$或$j$最大可達到$10^9$，無法直接作為并查集fa數組的下標，所以需要先對所有輸入的$i$與$j$進行離散化。由于每組數據輸入的約束條件的數量$n\le 10^5$，每一個約束條件最多新增兩個變量編號。因此在對變量編號進行離散化后，最多存在$2?10^5$個元素，離散化后的數值的范圍為$1～2?10^5$，可以作為fa數組的下標。

• 先遍歷所有約束。對于$x_i=x_j$，那么可以認為$x_i$與$x_j$同屬于一個集合，將$x_i$與$x_j$所在的集合合并。
• 再次遍歷所有約束，對于$x_i\ne x_j$，而且$x_i$與$x_j$已屬于同一集合，那么該問題中的約束條件無法都被滿足，輸出NO。

當看完所有約束后，如果沒有輸出NO，則以上約束條件可以同時滿足，輸出YES。

【題解代碼】

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int i, j, e;
};
vector<Node> op;
vector<int> t;
int fa[2*N];//不同的變量編號最多有2N個，因此并查集fa數組長度設為2N 
void init()
{for(int i = 1; i < 2*N; ++i)fa[i] = i;
}
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] = find(y);
}
void discretization()
{sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for(Node &p : op){p.i = upper_bound(t.begin(), t.end(), p.i)-t.begin();//離散化后，變量編號范圍為1~2*10^5 p.j = upper_bound(t.begin(), t.end(), p.j)-t.begin();}
}
bool isMatch()//是否可以滿足給定的所有約束 
{for(Node p : op) if(p.e == 0 && find(p.i) == find(p.j))return false;return true;
}
int main()
{int tn, n, i, j, e;cin >> tn;while(tn--){op.clear();t.clear();init();cin >> n;for(int k = 1; k <= n; ++k){cin >> i >> j >> e;op.push_back(Node{i, j, e});t.push_back(i);t.push_back(j);}discretization();for(Node p : op) if(p.e == 1)//如果是xi=xj merge(p.i, p.j);cout << (isMatch() ? "YES" : "NO") << '\n';}return 0;
}