这题我没看见数据范围,就直接写了,其实思路差不多,把所有相等的放在一个集合里面,然后看看不等的,在不在同一个集合里面,在就是no,不在就是yes
但是这个数据范围是1e9,直接做空间不够用,但是n就是数的总个数才2e5个,所以可以想到离散化,离散化有两种:保序和不保序的,保序的看看基础课吧,我忘记了QAQ
不保序的就是把这些数对应到一个属于它们的编号,就可以了,按照编号来对应数字,我喜欢QAQ
还有要用scanf555,cin被卡了
详细看代码:
#include<iostream> #include<cstdio> #include<map> using namespace std; const int N=2e6+10; struct mess{ int x,y,e; }a[N]; int n; int p[N]; map<int,int> mp;//对应着某个数的编号 int get(int x) { if(!mp[x]) { n++; mp[x]=n; } return mp[x]; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main(){ int T; scanf("%d",&T); while(T--) { n=0; mp.clear(); int m; scanf("%d",&m); for(int i=0;i<m;i++) { int x,y,e; scanf("%d%d%d",&x,&y,&e); a[i]={get(x),get(y),e};//一一映射到代表这个数的编号并且存在结构体里面 } for(int i=1;i<=n;i++) p[i]=i; for(int i=0;i<m;i++) { if(a[i].e) { int xx=find(a[i].x),yy=find(a[i].y); p[xx]=yy; } } int f=1; for(int i=0;i<m;i++) { if(!a[i].e) { if(find(a[i].x)==find(a[i].y)) { f=0; break; } } } if(f) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }