算法提高之程序自動分析

• 核心思想：并查集 + 離散化

  • 因為不是每個數都會用到 所以離散化一下**(不需要保留順序)**
  • 對于每一個值為1的等式 優先處理
  • 之后處理值為0的等式時 若ab已經連在一起 即為矛盾

•   #include <iostream>#include <cstring>#include <algorithm>#include <unordered_map>using namespace std;const int N = 200010;int p[N];int n,m,T;unordered_map<int,int> S;struct Query{int x, y, e;}query[N];int find(int x)  // 并查集{if (p[x] != x) p[x] = find(p[x]);return p[x];}int get(int x)  //離散化{if(S.count(x) == 0) S[x] = ++n;return S[x];}int main(){cin>>T;while(T--){n = 0;S.clear();cin>>m;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;query[i] = {get(a),get(b),c};}for(int i=0;i<=n;i++) p[i] = i;for(int i=0;i<m;i++){if(query[i].e == 1)  //1的優先處理{int pa = find(query[i].x),pb = find(query[i].y);p[pa] = pb;}}bool has_conflict = false;for(int i=0;i<m;i++){if(query[i].e == 0){int pa = find(query[i].x),pb = find(query[i].y);if(pa == pb){has_conflict = true;break;}}}if (has_conflict) puts("NO");else puts("YES");}}