私人网站服务器,学校网站建设软件推荐,缓存 wordpress 加速,seo赚钱吗正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1955 题目大意
给出若干个关系#xff0c;xi≠xj or xixjxi≠xjorxixj#xff0c;然后求是否全部都满足。 解题思路
首先由于数据较大#xff0c;所以我们先离散化#xff0c;然后用并查集。…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP1955 题目大意
给出若干个关系xi≠xj or xixjxi≠xjorxixjx_i\neq x_j\ \ \ or\ \ \ x_i=x_j然后求是否全部都满足。 解题思路
首先由于数据较大所以我们先离散化然后用并查集。先处理所有等于的关系然后不等于的再判断。 code
#includecstdio
#includealgorithm
#define N 1000010
using namespace std;
struct node{int x,y,t;
}a[N];
int n,uniq[2*N],f[2*N],t;
bool cmp(node x,node y)
{return x.ty.t;
}
int find(int x)
{if(f[x]!x) return f[x]find(f[x]);return x;
}
int main()
{scanf(%d,t);for(int ti1;tit;ti){scanf(%d,n);for(int i1;in;i){scanf(%d%d%d,a[i].x,a[i].y,a[i].t);uniq[i]a[i].x;uniq[in]a[i].y;}//以上为去重stable_sort(uniq1,uniq12*n);int munique(uniq1,uniq12*n)-(uniq1);//以上为离散化for(int i1;im;i) f[i]i;//初始化并查集for(int i1;in;i){a[i].xlower_bound(uniq1,uniq1m,a[i].x)-(uniq1),a[i].ylower_bound(uniq1,uniq1m,a[i].y)-(uniq1);}//以上为找到离散化之后的位置stable_sort(a1,a1n,cmp);bool flag0;for(int i1;in!flag;i){int fafind(a[i].x),fbfind(a[i].y);if(a[i].t) f[min(fa,fb)]max(fa,fb);//链接else if(fafb) printf(NO\n),flagtrue;//判答案}if(!flag) printf(YES\n);}
}
