[洛谷 1955,loj 2129][NOI2015]程序自动分析

题目链接

https://www.luogu.org/problem/P1955

题解

毫无悬念，这是一道签到题。

如果把所有变量看作一个点，那么相等关系就是在这两个点之间连一条边，而不等关系不与相等关系矛盾的必要条件则是：两个点不能处在同一集合中。

于是我们可以用并查集来维护这样的一个系统：如果给出一个相等关系，就合并两个集合，将所有的不等关系存储起来，在最后处理不等关系，如果两个点处于同一集合，那么这样的不等关系就不能满足。

PS:

1. 由于变量下标的范围达到了 \(10^9\)，所以需要离散化处理。
2. 最好不要用 map 来偷懒，本蒟蒻在洛谷上交了个 \(90\) 分（第二个点一直被卡，但在bzoj上却能AC），最后吸了氧总算AC了。
3. 用 C++11 的 unordered_map 来代替 map 也可以 AC（unordered_map 基于 hash，在不需要排序操作的时候效率比 map 快，但很有可能会被特别设计的数据卡掉）。
4. 这次被卡常的经验说明了：STL 常数很大，有时确实会被卡常。所以能手写数据结构的话就不要冒着被卡的风险写 TLE 了（如果允许吸氧，能用 STL 偷懒的情况下何乐而不为呢，就是调试会很麻烦）。

#include <cstdio>
#include <algorithm>
#include <unordered_map>//一定要以c++11标准编译
#include <cstring>
using namespace std;
unordered_map<int,int> num;//利用hash的unordered_map可以大大降低常数
int fa[200005];
int tj[100005][2];
int find(int a)//用递归写会爆栈，所以这里用非递归写了 
{
 int r=a;
 while(r!=fa[r])
  r=fa[r];
 int i=a,j;
 while(i!=r)
 {
  j=fa[r];
  fa[i]=r;
  i=j;
 }
 return r;
}
void unionn(int i,int j)
{
 fa[j]=i;
}
void setfa()
{
 for(int i=1;i<=200000;i++)
  fa[i]=i;
}
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int cnt=0,cntt=0;
  num.clear();
  memset(tj,0,sizeof(tj));
  setfa();
  int n;
  scanf("%d",&n);
  for(int k=1;k<=n;k++)
  {
   int i,j,e;
   scanf("%d%d%d",&i,&j,&e);
   if(num[i]==0)num[i]=++cnt;//map大法好，但常数确实大了 
   if(num[j]==0)num[j]=++cnt;//可以试试unordered_map？ 
   if(e)unionn(find(num[i]),find(num[j]));
   else
   {
    cntt++;
    tj[cntt][0]=num[i];
    tj[cntt][1]=num[j];
   }
  }
  int flag=1;
  for(int i=1;i<=cntt;i++)
   if(find(tj[i][0])==find(tj[i][1]))
   {
    puts("NO");
    flag=0;
    break;
   }
  if(flag)puts("YES");
 }
 return 0;
}