这道题一眼就知道是并查集,创个int型数组按步骤写就好了。
哈哈如果这样想简单了就错了。看一下题目的数据范围:
编号最大值达到了\(10^9\),但是不同的编号最多只有\(2\times 10^5\)个,问题就出在这里。如果创建一个有10亿个元素的int数组,那内存明显不够用。所以需要将数组离散化。这里使用STL的unordered_map来储存,key为结点的编号,value为父结点的编号。(为什么不能用map?因为map的find操作是对数时间的,而为了达到数组随机存储的常数时间,需要使用unordered_map,它使用了哈希表,可以在常数时间内存取)
所以,算法的流程如下:
维护两个容器father和neq,前者储存并查集,后者储存不相等关系的结点编号。
创建一个函数add,若结点已经在并查集中,不做任何处理;否则将其加入并查集并初始化。
每读入一个表达式,就进行判断:若表达式的符号为=
,就使用add函数处理表达式的两个结点编号,然后进行union操作;否则的话,使用add函数处理表达式的两个结点编号,然后将这两个结点的编号加入neq容器。
遍历完所有表达式后,遍历neq容器中的所有编号对,对其进行find操作。若存在一堆编号在同一个set中,说明条件不可满足,退出循环。
注意,由于数据量较大,所以应该对并查集进行路径压缩,推荐使用递归的方法来书写。同时,数据量大所以要加入该语句从而加速I/O
ios::sync_with_stdio(false);
代码如下:
#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<unordered_map> #include<vector> using namespace std; int t; //使用哈希表离散化储存数据,key为结点编号,value为父结点的编号,注意,每轮循环结束要clear unordered_map<int, int> father; //储存当前判定的所有不等于条件,注意,每轮循环结束要clear vector<pair<int, int>> neq; //使用路径压缩 int findfather(int i) { if (father[i] == i) return i; int root = findfather(father[i]); father[i] = root; return root; } //判断两个节点是否在同一个set中 bool find(int i,int j) { return findfather(i) == findfather(j); } //union两个set void myunion(int i,int j) { if (!find(i, j)) { int r1, r2; r1 = findfather(i); r2 = findfather(j); father[r2] = r1; } } //将i,j加入father,若已存在则不处理,否则将其加入并初始化 void add(int i, int j) { if (father.find(i) == father.end()) { father.insert(pair<int, int>(i, i)); } if (father.find(j) == father.end()) { father.insert(pair<int, int>(j, j)); } } int main(void) { //关闭同步,加速io ios::sync_with_stdio(false); cin >> t; while (t-- > 0) { //条件数 int qnum; cin >> qnum; int i, j, e; while (qnum-- > 0) { cin >> i >> j >> e; if (e == 1) { //先离散化储存,然后union add(i, j); myunion(i, j); } else if (e == 0) { //先离散化储存,然后存储不相等的数据 add(i, j); neq.push_back(pair<int, int>(i, j)); } } //遍历所有不等于的条件,判断节点是否在一个set中 bool flag=true; for (int k = 0; k < neq.size(); k++) { int i, j; i = neq[k].first; j = neq[k].second; if (find(i, j)) { flag = false; break; } } if (flag) cout << "YES" << endl; else cout << "NO" << endl; //清空father,neq容器 father.clear(); neq.clear(); } }